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

比赛题目很简单嘛，大一的随便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;
}