比赛地址

牛客OJ

Pro: 3/4/10

Rank: 117/1172

[B] Basic Gcd Problem

题意&题解

签到题

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
long long int ans, c;
const long long int mo = 1000000007;
int n, p[1000005];
int main() {
    for (int i = 2; i <= 1000000; i++) if (p[i]==0) {
        int up = 1000000/i;
        for (int j = 1; j <= up; j++) p[i*j] = i;
    }
    int t; scanf("%d", &t); while(t--) {
        scanf("%d%d", &n, &c); ans = 1;
        while(n!=1) {
            ans = ans*c%mo;
            n/=p[n];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

[F] Finding the Order

题意&题解

签到题

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int n, a, b, c, d;
int main() {
    int t; scanf("%d", &t); while(t--) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        if (a+d>b+c) printf("AB//DC\n");
        else printf("AB//CD\n");
    }
    return 0;
}

[G] Harder Gcd Problem

题意

给出一个整数n,要求从1到n中选出一些数构成两个大小相同的集合,且集合的元素可以两两配对,每一对的gcd大于1.求集合最大是多少.

题解

首先,1和大于\frac{n}{2}的质数一定不会被放到集合中.剩下的所有数就是答案.

考虑贪心配对,从大到小枚举质数p,然后检查该质数中没有匹配的数,让它们两两配对.如果最后会剩下一个,就余下2p.

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int n, p[200005], ansx[100005], ansy[100005], cnt, now[100005], s[200005], tot;
int main() {
    for (int i = 2; i <= 200000; i++) if (p[i]==0) {
        int up = 200000/i;
        for (int j = i; j <= up; j++) p[i*j] = 1;
    }
    int t; scanf("%d", &t); while(t--) {
        scanf("%d", &n);
        cnt = 0;
        for (int i = 1; i <= n; i++) s[i] = 1;
        for (int i = n/2; i > 2; i--) if (p[i]==0) {
            tot = 0;
            int up = n/i;
            for (int j = 1; j <= up; j++) if (s[i*j]) {
                now[++tot] = i*j;}
            if (tot%2) {
                cnt++;
                ansx[cnt] = now[1];
                ansy[cnt] = now[3];
                s[now[1]] = s[now[3]] = 0;
                for (int j = 5; j <= tot; j += 2) {
                    cnt++;
                    ansx[cnt] = now[j-1];
                    ansy[cnt] = now[j];
                    s[now[j-1]] = s[now[j]] = 0;
                }
            } else {
                for (int j = 2; j <= tot; j += 2) {
                    cnt++;
                    ansx[cnt] = now[j-1];
                    ansy[cnt] = now[j];
                    s[now[j-1]] = s[now[j]] = 0;
                }
            }
        }
        tot = 0; int up = n/2;
        for (int j = 1; j <= up; j++) if (s[2*j]) {
            now[++tot] = 2*j; s[2*j] = 0; }
        for (int j = 2; j <= tot; j += 2) {
            cnt++;
            ansx[cnt] = now[j-1];
            ansy[cnt] = now[j];
        }
        printf("%d\n", cnt);
        for (int i = 1; i <= cnt; i++) printf("%d %d\n", ansx[i], ansy[i]);
    }
    return 0;
}

[I] Investigating Legions

题意

有n个人隶属于m个组织,现在告诉你这些人两两之间是否属于同一个组织,求每个人属于组织的情况.给出的每一个信息都有\frac{1}{S}的概率是错的.

题解

乱搞.

随便找一个连通块出来,然后统计下两两之间的关系.当一个人与超过三分之一的连通块的人数都有关系时,就认为他们是一个组织的.

代码

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 310
#define INF 0x3f3f3f3f
using namespace std;

int T,i,n,s,m,j,cnt;
int a[N],l[N][N],b[N];
char c[N*N];

vector <int> v;
map <int,int> M;

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)    {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)  p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Work(){
    reg int i=0,j=0,s=n,id=1;
    for (i=1;i<=n;i++)   a[i]=b[i]=0;
    for (i=1;i<=n;i++){
        if (!a[i]){
            v.clear();  v.push_back(i);
            for (j=1;j<=n;j++)
                if (l[i][j])    v.push_back(j);
            memset(b,0,sizeof(b));
            for (j=1;j<=n;j++)
                for (auto k : v)
                    if (l[k][j])    b[j]++;
            for (j=1;j<=n;j++)   if (b[j]>=v.size()/3)    a[j]=id;
            id++;
        }
    }
    M.clear();  id=1;
    for (i=1;i<=n;i++)
        if (!M[a[i]])   M[a[i]]=id++;
    for (i=1;i<=n;i++)   printf("%d ",M[a[i]]-1);
    putchar(10);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();   s=read();
        scanf("%s",&c);
        if (n<60){
            for (i=1;i<=n;i++)   putchar(48),putchar(' ');
            putchar(10);
            continue;
        }
        cnt=0;
        for (i=1;i<=n;i++)
            for (j=i+1;j<=n;j++)
                l[i][j]=l[j][i]=c[cnt++]-48;
        Work();
    }
    return 0;
}

总结

式子还是推的有点慢,乱搞的姿势水平也有待提高(?).