Codeforces Round#572(Div 2)

~~这场比较简单~~，深夜肝题，精神抖擞.jpg，不过涨分就很舒服

A. Keanu Reeves

题意: 是给定一个只含0和1的串，问能否能分成最少的子串，并且这些子串的0和1数量不相等

解析: 如果该串本身01数量不等，直接输出，否则就分成两部分就好，第一个字符单独一部分，剩下的为另一部分(我的代码是最后一个字符单独一部分)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[200];
int n;
int main(){
    scanf("%d",&n);
    scanf("%s",s);
    int cnt0=0,cnt1=0;
    for(int i=0; i<n; i++){
        if(s[i] == '0') cnt0++;
        else cnt1++;
    }
    if(cnt0 != cnt1){
        printf("1\n%s\n",s);
    }
    else{
        puts("2");
        for(int i=0; i<n-1; i++){
            printf("%c",s[i]);
        }
        printf(" %c\n",s[n-1]);
    }
}

B. Number Circle

题意: 给定一个序列，问你能否组成一个首尾相接循环的序列，使得每个数都比相邻的两个数的和小

解析: 对数组a首先排序，直接从最后一个元素a[n]开始找，找从前面找a[i]，使得a[n-1]+a[i] > a[n]，如果找到a[i]，那么序列就是a[n-1] a[n] a[i] a[1] … a[n-2] (假设i不是1或者n-2)，具体看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n;
int a[maxn];
int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    for(int i=0; i<n-2; i++){
        if(a[i]+a[n-2] > a[n-1]){
            puts("YES");
            printf("%d %d %d",a[n-2],a[n-1],a[i]);
            for(int j=0; j<n-2; j++){
                if(j!=i) printf(" %d",a[j]);
            }
            puts("");
            return 0;
        }
    }
    puts("NO");
}

题意: 有这么一个操作，对于a[i], a[i+1],…,a[j],其中，j-i+1是2的幂次方，然后对于每两个数，相加得到一个新数，然后个数就变成了原来的一半，比如说{1,2,3,4}，经过一次变换之后就变成了{3，7},一直操作直到个数为1; 然后对于每次操作，如果相加得到的新数大于10，我就能得到一颗糖，并且将新数对10取模; 然后我有k次询问，对于区间内的数，经过若干次操作之后，我能拿多少糖。

解析: 题目给的限制，每个数小于10，我只要统计区间内的总数，然后除以10取整就是答案，证明略。~~(盲猜结论直接莽一发)~~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n;
int a[maxn];
int dp[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
        dp[i]=dp[i-1]+a[i];
    }
    int m,l,r;
    scanf("%d",&m);
    while(m--){
        scanf("%d %d",&l,&r);
        printf("%d\n",(dp[r]-dp[l-1])/10);;
    }
}

D1. Add on a Tree

题意: 有一棵树，然后有一种操作，任意选择两个叶子节点，然后得到一条路径，我能在这条路径上加上某个实数(初始化每条边都是0)，这样每条边都有一个数，问对于任意一组边上的数，我能否通过有限次操作实现

解析: 透过题目看本质，其实就是一道水题，当一个节点只连接两条边，就是NO，否则就是YES

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int vis[maxn];
int main(){
    int n,x,y;
    scanf("%d",&n);
    int s=0;
    memset(vis,0,sizeof vis);
    for(int i=0; i<n-1; i++){
        scanf("%d %d",&x,&y);
        vis[x]++;
        vis[y]++;
    }
    bool flag=true;
    for(int i=1; i<=n; i++){
        if(vis[i] == 2){
            flag=false;
            break;
        }
    }
    if(flag) puts("YES");
    else puts("NO");
}

E. Count Pairs

题意: 有一个数组a，给定一个素数p和一个小于p的数k，问能找到多少组(i,j),使得 $(a_i+a_j)*(a_i^2+a_j^2) \equiv k\ mod \ p$

解析: 两边同时乘$a_i - a_j$，就变成了$(a_i^4-a_j^4)$ $ \equiv $ $(k * a_i-k * a_j)$ $\ mod \ p$ ,转换就是$({a_i^4}-k * {a_i})$ $ \equiv $ $(k * {a_j^4} - k * {a_j}) $ $\ mod \ p$

只要另$b_i = a_i^4 - k* a_i$ 就可以通过map统计个数了,注意取模

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll n,p,k;
map<ll,ll>ma;
int main(){
    scanf("%lld %lld %lld",&n,&p,&k);
    ll cnt=0;
    for(ll i=0; i<n; i++){
        scanf("%lld",&a);
        b=(a*a%p*a%p*a%p-a*k%p+p)%p;
        //printf("%lld %lld\n",b,(a*a*a*a-a*k+p)%p);
        ma[b]++;
        cnt+=(ma[b]-1);
    }
    printf("%lld\n",cnt);
}

A. Keanu Reeves

B. Number Circle

C. Candies!

D1. Add on a Tree

E. Count Pairs