cf Round 603

时间：2021-08-27 22:59:13

A.Alternative Thinking(思维)

给出一个01串，你可以取反其中一个连续子串，问取反后的01子串的最长非连续010101串的长度是多少。

我们随便翻一个连续子串，显然翻完之后，对于这个连续子串而言，最后的答案一定不会变优。
只会对你翻的左端点和右端点相邻的数字产生贡献。我们计左端点为l，右端点为r。
而且要想最大化贡献，必须要使得这个a[l]和a[l-1]一样。a[r]和a[r+1]一样。
那么我们只要找到可以使这个贡献获得最大时的条件就行了。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

# define fi first

# define se second

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

typedef unsigned long long ULL;

int _MAX(int a, int b){return a>b?a:b;}

int _MIN(int a, int b){return a>b?b:a;}

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

char s[N];

int main ()

{

    int n, cnt=, ans1=, ans2=;

    char f=' ';

    scanf("%d%s",&n,s+);

    FOR(i,,n) {

        if (s[i]=='') ans2=ans1+;

        else ans1=ans2+;

        if (f==s[i]) cnt++;

        f=s[i];

    }

    int ans=max(ans1,ans2);

    if (cnt==) ans+=;

    else if (cnt>=) ans+=;

    printf("%d\n",ans);

    return ;

}

B.Moodular Arithmetic(数论)

告诉你p和k，其中(0<=k<=p-1)，x属于{0,1,2,3,....,p-1}，f函数要满足f(k*x%p)=k*f(x)%p,f(x)的范围必须在[0,p-1]内，问这样的f函数有多少个

先观察小情形。
k=0时，此时有f(0)=0.即除了0其他可以随便乱取。那么我们得到ans=p^(p-1).
k=1时，此时有f(x)=f(x).此时随便乱取。那么我们得到ans=p^p.
后面我们发现就不好办了。
但是我们发现f(k*k*x)=k*f(k*x)%p=k*(k*f(x)%p)%p.
这不是乘法取模吗。那么则有f(k^n*x%p)=(k^n)%p*f(x)%p.
我们要是能使k^n%p=1就好了，那么就会有n个数在一个环上面。我们令n最小。
那么n就是k关于p的一个阶。
因为f(0)=0,那么答案就是p^((p-1)/n).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

# define fi first

# define se second

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

typedef unsigned long long ULL;

int _MAX(int a, int b){return a>b?a:b;}

int _MIN(int a, int b){return a>b?b:a;}

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

LL muti_mod(LL a,LL b,LL c)

{

    a%=c; b%=c;

    LL ret=;

    while (b) {

        if (b&){ret+=a; if (ret>=c) ret-=c;}

        a<<=;

        if (a>=c) a-=c;

        b>>=;

    }

    return ret;

}

LL pow_mod(LL x,LL n,LL mod)

{

    if (n==) return x%mod;

    int bit[], k=;

    while (n) bit[k++]=n&, n>>=;

    LL ret=;

    for (k=k-; k>=; --k){

        ret=muti_mod(ret,ret,mod);

        if (bit[k]==) ret=muti_mod(ret,x,mod);

    }

    return ret;

}

int eul(LL p, LL k)

{

    FO(i,,p) if ((p-)%i==&&pow_mod(k,(LL)i,p)==) return i;

}

int main ()

{

    LL p, k;

    scanf("%lld%lld",&p,&k);

    if (k==) printf("%lld\n",pow_mod(p,p-,MOD));

    else if (k==) printf("%lld\n",pow_mod(p,p,MOD));

    else {

        int temp=eul(p,k);

        printf("%lld\n",pow_mod(p,(p-)/temp,MOD));

    }

    return ;

}

C.Lieges of Legendre(SG函数)

变形版nim游戏，操作有两个，1.取出一个石子。2.把一堆偶数个石子变成k堆偶数/2个石子。

分析:
抽象成DAG，这个DAG的顶点度数最大为2，打sg表找规律。
发现k为偶数时很简单。 k为奇数时。模拟求sg函数，可以递归的求出sg。
复杂度O(n*logai).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

# define fi first

# define se second

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

typedef unsigned long long ULL;

int _MAX(int a, int b){return a>b?a:b;}

int _MIN(int a, int b){return a>b?b:a;}

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

int n, k, a[]={,,,,,,};

int find(int x)

{

    if (k%==) {

        if (x<=) return x;

        else return x%==;

    }

    else {

        if (x<=) return a[x];

        if (x&) return ;

        else {

            if (find(x/)==) return ;

            else return ;

        }

    }

}

int main ()

{

    int temp, ans=;

    scanf("%d%d",&n,&k);

    while (n--) scanf("%d",&temp), ans^=find(temp);

    puts(ans?"Kevin":"Nicky");

}

D.Ruminations on Ruminants(数学)

枚举出三个点之后判定是否过原点还是可以的.但是不能枚举.
只知道相加180这个限制是不好想办法的.
所以转化成:远点向直线做垂线,只有三个垂足在同一条直线上的时候,才行.
那么我们先做找出来垂足,然后数三个点在一条直线的三元组个数.
转化一下,就是两点确定一条直线,然后再看每一条直线上有多少个点,用组合数算.
但是这样不好写(还要转成直线的方程),i j k(i < j < k), 我们枚举i,要求j和k相对于i的斜率必须一样. 如果有重合的点,那么任意一个第三个点都可以.
注意,要全部用整数,先联立方程算出来垂足,用分子分母表示,然后求斜率减之后也化成标准的形式.

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <map>

using namespace std;

typedef long long ll;

const int maxn =  + ;

int n, a[maxn], b[maxn], c[maxn], ac[maxn], bc[maxn], a2b2[maxn];

ll res;

struct Point {

    ll x, y;

};

ll gcd(ll x, ll y) {

    if(y == )

    return x;

    return gcd(y, x % y);

}

Point getStand(Point t) {

    if(t.x == ) {

    if(t.y == )

        return t;

    t.y = ;

    return t;

    }

    else if(t.y == ) {

    t.x = ;

    return t;

    }

    ll d = gcd(abs(t.x), abs(t.y));

    t.x /= d;

    t.y /= d;

    if(t.x <  && t.y <  || t.x >  && t.y < ) {

    t.x = -t.x;

    t.y = -t.y;

    }

    return t;

}

void solve() {

    for(int i = ; i <= n; i++) {

    ac[i] = a[i] * c[i];

    bc[i] = b[i] * c[i];

    a2b2[i] = a[i] * a[i] + b[i] * b[i];

    }

    res = ;

    for(int i = ; i <= n; i++) {

    map<ll, map<ll, ll> > mp;

    int same = , ans = ;

    for(int j = i + ; j <= n; j++) {

        Point t;

        t.x = (ll)a2b2[j] * (ll)ac[i] - (ll)a2b2[i] * (ll)ac[j];

        t.y = (ll)a2b2[j] * (ll)bc[i] - (ll)a2b2[i] * (ll)bc[j];

        t = getStand(t);

        if(t.x ==  && t.y == ) {

        same++;

        ans += (j - i - );

        }

        else {

        ans += mp[t.x][t.y] + same;

        mp[t.x][t.y]++;

        }

    }

    res += ans;

    }

    printf("%I64d\n", res);

}

int main() {

  //  freopen("D.txt", "r", stdin);

    while(scanf("%d", &n) != EOF) {

    for(int i = ; i <= n; i++) {

        scanf("%d%d%d", &a[i], &b[i], &c[i]);

    }

    solve();

    }

    return ;

}

E.Pastoral Oddities(待填坑)

相关文章