• CCPC威海 J(博弈),C(计算几何) CF1442A(差分,DP) CF847C


    CJG三道题属于标准的铜牌题。G是个打表?队友说可以不写我就放了。

    就是威海题面感觉很迷惑,A题反复强调冠军选手不改位置让人以为其他选手可以改位置?要命的是这个错误题意仍然可以过掉样例和前10组测试用例。。。。

    然后J的博弈有一个occurrences,这个其实可以理解为出现过,理应加个current说明。

    J. Eat, Sleep, Repeat

    题意:两人轮流数组中选一个数让这个数减一,对于这个数组有k个限制,每个限制规定某个数字最多出现几个,现在有Pico和FuuFuu轮流进行减一操作,当数组全为0或者操作之后不满足限制时视为目前的操作者失败。

    给定n个数的数组和k个限制,请问谁会赢。

    思路:很简单,最终状态是确定的,最终步数也就确定了,需要注意的有两点,1.当某个数限制时0的时候他就是一个“隔断”,因为比这个限制大的数不能再继续减小了。2.对于0,这是一个特殊的隔断。

    所以我们需要做的就是:分出区间,把数组所有的值尽可能变小,然后判断奇偶,奇数就是pico赢否则是fuufuu赢了

    ACcode,这个代码用64位编译器会出现错误,不知道为啥,普通的编译器就是ok的。

    #include 
    using namespace std;
    #define int long long
    #define endl '\n'
    const int N = 1e5+100;
    int a[N];
    signed main()
    {
        cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
        int t;
        for(cin>>t;t;t--)
        {
            int n,k;
            cin>>n>>k;
            map<int,int>lim;
            vector<int> zero;
            map<int,int>ex;
            for(int i=1;i<=n;i++)
            {
                cin>>a[i];
                lim[a[i]]++;
            }
            for(int i=1;i<=k;i++)
            {
                int x,y;
                cin>>x>>y;
                ex[x]=1;
                lim[x]=y;
                if(y==0)
                {
                    zero.push_back(x);
                }
            }
            zero.push_back(1e9+7);
            sort(a+1,a+n+1);
            sort(zero.begin(),zero.end());
            int pos=-1;
            int mx=0;
            int sum=0;
            for(int i=1;i<=n;i++)
            {
                 while(pos<zero.size()&&zero[pos+1]<a[i])
                 {
                     pos++;
                     mx=zero[pos]+1;
                 }
                 if(lim[mx])
                 {
                     sum+=a[i]-mx;
                     lim[mx]--;
                 }
                 else
                 {
                     while(!lim[mx]&&ex[mx])
                     {
                         mx++;
                     }
                     sum+=a[i]-mx;
                     lim[mx]--;
                 }
            }
            if(sum&1)
            {
                cout<<"Pico"<<endl;
            }
            else
            {
                cout<<"FuuFuu"<<endl;
            }
        }
        return 0;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    C. Grass

    题意:我们第定义“草”是这样的五个点构成的图
    五个点有一个点是A,他和另外4个点连线,一共生成AB AC AD AE四条线段,如果四条线段的任意两条的交点只有A一个,那么成这五个点构成的图是草

    思路:换成人话,找五个点,有一个点满足分别和另外四个连线,这四条线上除了端点都没别的点了。

    那么显然只要存在不共线的五个点就一定是存在解的,然后就是如何去确定A点是谁,根据上面的分析,我们对这五个点枚举点A即可,每次枚举还要枚举另外剩下的四个点,构成线段后再看看剩下的三个点在不在线段上就可以了。

    比较尴尬的是,虽然第一次写AC了,我想题解写一个用double记录坐标,但是会wa,不懂为啥。

    #include 
    using namespace std;
    #define double long double
    #define endl '\n'
    const int N = 1e5+100;
    const double eps=1e-10;
    int a[N],b[N];
    struct node
    {
        int x,y;
    };
    bool check(node x,node y,node z)//三点共线
    {
        if((x.y-y.y)*(x.x-z.x)==(x.x-y.x)*(x.y-z.y))
            return true;
        return false;
    }
    node point[N];
    
    void slove()
    {
            int n;
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                cin>>point[i].x>>point[i].y;
            }
            if(n<5)
            {
                cout<<"NO"<<endl;
                return ;
            }
            node p[10]={point[0],point[1],point[2],point[3],point[4]};
            for(int i=5;i<=n;i++)
            {
                p[5]=point[i];
                if(!check(p[1],p[2],p[3])||!check(p[1],p[2],p[4])||!check(p[1],p[2],p[5]))
                {
                    cout<<"YES"<<endl;
                    for(int j=1;j<=5;j++)
                    {
                        bool falg=true;
                        for(int k=1;k<=5;k++)
                        {
                            if(k==j)
                                continue;
                            for(int l=1;l<=5;l++)
                            {
                                if(l==k||l==j)
                                    continue;
                                if(check(p[j],p[k],p[l])&&(p[l].x>=min(p[k].x,p[j].x)&&p[l].x<=max(p[k].x,p[j].x)&&p[l].y>=min(p[k].y,p[j].y)&&p[l].y<=max(p[k].y,p[j].y)))
                                {
                                    falg=false;
                                    break;
                                }
                            }
                            if(!falg)
                            {
                                break;
                            }
                        }
                        if(falg)
                        {
                            cout<<p[j].x<<" "<<p[j].y<<endl;
                            for(int k=1;k<=5;k++)
                            {
                                if(k==j)
                                    continue;
                                cout<<p[k].x<<" "<<p[k].y<<endl;
                            }
                            return ;
                        }
                    }
                }
            }
            cout<<"NO"<<endl;
    }
    int main()
    {
        cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    	int t;
    	for(cin>>t;t;t--)
        {
            slove();
        }
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    来两个1800的思维

    A. Extreme Subtraction

    题意:给定一个数组,每次可以取前缀后者后缀让其整体减一,请判断是否可以将整个数组变成0

    这个题做法貌似很多,贪心,DP,差分都可以,但是我DP写的又长又臭,虽然A但是显然差分才应该是正解。

    思路:对于整体的区间减加操作不可以忘记差分啊!

    设数组d是差分数组
    对于前缀减一显然就是
    d[1]-- d[i+1]++

    对于后缀的显然就是
    d[i]-- d[n+1]++

    差分数组的前缀和就是原数组,所以原数组变0就是差分数组变0
    又发现让d[n+1]++是不会产生影响的,所以得数可以让任意位置的d[i]变为0的结论,但是让负数变成0只有前缀操作可以,

    所以最后就变成了,a[1]=d[1]要满足大于所有差分数组中负数绝对值的和。

    #include
    using namespace std;
    const int N = 1e6+100;
    int a[N],b[N];
    signed main()
    {
        cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
        int t;
        for(cin>>t;t;t--)
        {
            int n;
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                cin>>a[i];
                b[i]=a[i]-a[i-1];
            }
            int cnt=0;
            for(int i=1;i<=n;i++)
            {
                if(b[i]<0)
                {
                    cnt+=b[i]*-1;
                }
            }
            if(a[1]>=cnt)
            {
                cout<<"Yes";
            }
            else
            {
                cout<<"No";
            }
            if(t!=1)
                cout<<'\n';
        }
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    C. Sum of Nestings
    嘿嘿,这题队友用的DFS,我直接上思维把他给秒了

    题意:请你构造长度为n*2的合法括号序列,满足内联括号数量为k
    内联括号:被包含在某个括号内部的括号叫做这个括号的内联括号

    例如
    ((())),这样内联括号数量为3个

    如果能构造,请输出你构造的括号序列,否则输出No

    思路:显然我们能够构造的数目最多的就是左边n个(右边n个),这里还有个小结论,就是(越是靠左,越有可能被匹配上。

    那么观察最多这个,不难发现,最外层对答案的贡献是n-1,次外层n-2,以此类推最内层对答案贡献为0

    所以只要知道k和n*(n-1)/2的差值dis,将对应贡献加和为dis的几个括号匹配从大的括号变成最小的()就行了

    #include 
    
    using namespace std;
    #define int long long
    const int N = 1e6+100;
    int vis[N];
    signed main()
    {
        int n,k;
        cin>>n>>k;
        int maxx=n*(n-1)/2;
        if(k>maxx)
        {
            cout<<"Impossible"<<endl;
            return 0;
        }
        else
        {
            int dis=maxx-k;
            int now=n-1;
            int num=0;
            while(dis)
            {
                if(now>dis)
                {
                    now=dis;
                }
                vis[now+1]=1;
                dis-=now;
                now--;
                num++;
            }
            for(int i=n;i>=1;i--)
            {
                if(vis[i])
                {
                    cout<<"()";
                }
                else
                    cout<<"(";
            }
            for(int i=1;i<=n-num;i++)
            {
                cout<<")";
            }
        }
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
  • 相关阅读:
    STM32CubeMX学习笔记3-串口通信2(不定长数据)
    Git存储原理——Git对象
    什么是Fetch API?与传统的AJAX相比,有什么优势?
    BI行业分析思维框架 - 环保行业分析(三)三层经营分析框架
    socket编程中服务器端常用函数以及简单实现
    Linux下Cmake安装或版本更新
    Spring MVC简介及核心组件和调用流程理解
    信钰证券:积极因素不断积累 机构看多中长期市场
    NuGet包使用方法
    maven+Junit+jacoco的样例demo
  • 原文地址:https://blog.csdn.net/qq_35866893/article/details/127773227