新oj压力测试及水题娱乐赛（水水更健康）---题解

2019-11-06 07:09:16

字体：大中小

来源：转载

供稿：网友

比赛题目很简单嘛，大一的随便4题吧，大二的随便6题吧，感觉大二的普遍菜一点？比赛连接在这里点击打开链接

A：这个随机数是67,自己从1到100一个数一个数试也没有问题的啊，就第67就AC了

B：两层循环套着找一下就可以了，输出的时候找到一个就输一个就可以了，不要担心没有输完这种东西，文件输入输出，另外注意一下格式问题就可以了

#include <bits/stdc++.h> using namespace std; int main(){    int n,m;    char mp[25][25];    while(~scanf("%d%d",&n,&m)){        int cot = 0;        for(int i = 0;i < n;i++){            for(int j = 0;j < m;j++){                cin>>mp[i][j];                if(mp[i][j] == '@'&&cot != 0) PRintf(" (%d,%d)",i,j),cot++;                if(mp[i][j] == '@'&&cot == 0) printf("(%d,%d)",i,j),cot++;            }        }        if(cot == 0) puts("-1");        else puts("");    }    return 0;}
C：随便筛一下素数就可以了，0的时候输出sum就可以了
#include <bits/stdc++.h> using namespace std; bool is_prime(int n){    for(int i = 2;i * i <= n;i++)        if(n % i == 0) return false;    return true;} int main(){    int n;    int sum = 0;    while(~scanf("%d",&n)){        if(n == 0) {printf("%d/n",sum);break;}        else if(n == 1) continue;        else if(is_prime(n)) sum+=n;    }    return 0;}
D：判断是不是2的幂的时候要注意一下，这里使用位运算，i&(i-1)具体为什么这样写呢，大家可以去分别输出i和i-1的二进制值，然后两个做且运算，就可以明白为什么这样写了，预处理一下前缀和就可以了
#include <bits/stdc++.h> using namespace std;typedef long long ll; int main(){    int n,a[1005];    ll sum[1005];    memset(a,0,sizeof(a));    memset(sum,0,sizeof(sum));    for(int i = 1;i < 1005;i++){        if((i&(i-1)) == 0) a[i] = i;        else a[i] = -i;    }    for(int i = 1;i < 1005;i++)        sum[i] = sum[i-1]+a[i];    while(~scanf("%d",&n)){        printf("%d/n",sum[n]);    }    return 0;}
E：因为n <= 10，所以两层循环套一下就可以了，复杂度最坏也就1e6，要理解韩信点兵是什么意思，时间上就是给你总人数对某个数求余，然后剩下多少个人，循环去找一下，满足所有的条件才行，即第二层循环找完才可以，由于是找最小，找到了后我们直接输出就可以了
#include <bits/stdc++.h> using namespace std; int main(){    int n,l[100005],r[100005];    while(~scanf("%d",&n)){        memset(l,0,sizeof(l));        memset(r,0,sizeof(r));        for(int i = 0;i < n;i++)            scanf("%d%d",&l[i],&r[i]);        int i,j;        for(i = 1;i <= 100000;i++){            for(j = 0;j < n;j++){                if(i % l[j] != r[j]) break;            }            if(j == n) {printf("%d/n",i);break;}        }    }    return 0;} 
F：一个模拟题，输入比较恶心，但是还是比较好模拟的，具体看代码（这是一份比较短的代码）：
#include<stdio.h>#include<string.h>int main(){    char a,b,c,d,e[10],z[5],x[5],f,g;    int q,w,r,n,m;   while (scanf("%s %c,%c",z,&a,&b)!=EOF)    { gets(z);    scanf("%s %c %d;",x,&f,&n);      if (a==f) q=n; else w=n;    scanf("%s %c %d;",z,&g,&m);      if (a==f) w=m; else q=m;    while (1)    {  scanf("%s",e);     if (strlen(e)==4) break;      scanf("%c %c",&c,&d);      gets(z);      switch(e[0])      {       case 'A':if(a==d) q=q+w;                   else w=q+w;break;        case 'S':if(a==d) q=q-w;                   else w=w-q;break;        case 'M':if(a==d) q=q*w;                   else w=q*w;break;        case 'D':if(a==d) q=q/w;                   else w=w/q;break;      } }    printf("%d %d/n",q,w);}    return 0;}
G：给出n只袜子，最多k个颜色，一共m天，每天都要穿某两只袜子，不能让某一天穿不同颜色的手套，问至少改变多少只袜子的颜色。思路：把在同一天穿的袜子用并查集放到一起，然后找出最多的那种颜色，size-max即为这堆袜子至少要改的次数。两种解法，并查集，dfs：并查集解法：
#include <bits/stdc++.h>using namespace std;const int maxn = 2e5 + 5;int pre[maxn], a[maxn], b[maxn];vector<int> v[maxn];int Find(int x){    if(pre[x] != x) pre[x] = Find(pre[x]);    return pre[x];}void join(int x, int y){    pre[Find(y)] = Find(x);}int main(){    int n, m, k, x, y;    while(~scanf("%d%d%d", &n, &m, &k))    {        for(int i = 0;i <= maxn;i++)            v[i].clear();        for(int i = 1; i <= n; i++)            scanf("%d", &a[i]), pre[i] = i;        for(int i = 1; i <= m; i++)            scanf("%d%d", &x, &y), join(x, y);        int cnt = 1;        for(int i = 1; i <= n; i++)        {            if(pre[i] == i)                b[i] = cnt++;        }        for(int i = 1; i <= n; i++)        {            v[b[Find(i)]].push_back(a[i]);        }        int ans = 0;        for(int i = 1; i < cnt; i++)        {            int maxx = 0;            map<int, int> mm;            for(int j = 0; j < v[i].size(); j++)            {                mm[v[i][j]]++;                if(mm[v[i][j]] > maxx)  maxx = mm[v[i][j]];            }            ans += v[i].size() - maxx;        }        printf("%d/n", ans);    }    return 0;}dfs解法：#include<bits/stdc++.h>using namespace std;typedef long long ll;int n,m,k;int x[200005];vector<vector<int> >v;int cnt[200005];int ans,mxc,c;int vs[200005];void dfs1(int node){    vs[node]=1;    for(int i=0; i<v[node].size(); i++)    {        if(vs[v[node][i]]==0)        {            vs[v[node][i]]=1;            cnt[x[v[node][i]]]++;            if(cnt[x[v[node][i]]]>mxc)            {                mxc=cnt[x[v[node][i]]];                c=x[v[node][i]];            }            dfs1(v[node][i]);        }    }}void dfs2(int node){    vs[node]=2;    for(int i=0; i<v[node].size(); i++)    {        if(vs[v[node][i]]==1)        {            vs[v[node][i]]=2;            cnt[x[v[node][i]]]=0;            if(x[v[node][i]]!=c)                ans++;            x[v[node][i]]=c;            dfs2(v[node][i]);        }    }}int main(){    while(cin>>n>>m>>k)    {        ans=0;        memset(x,0,sizeof(x));        v.clear();        for(int i=0; i<n; i++)            cin>>x[i];        v.resize(n);        for(int i=0; i<m; i++)        {            int a,b;            cin>>a>>b;            a--,b--;            v[a].push_back(b);            v[b].push_back(a);        }        fill(cnt,cnt+200005,0);        fill(vs,vs+200005,0);        for(int i=0; i<n; i++)        {            if(vs[i]==0)            {                mxc=1;                c=x[i];                cnt[x[i]]++;                dfs1(i);                cnt[x[i]]--;                if(x[i]!=c)                {                    x[i]=c;                    ans++;                }                dfs2(i);            }        }        cout<<ans<<endl;    }    return 0;}