signed

QiShunwang

“诚信为本、客户至上”

UPC 2021个人训练赛第9场 题解

2021/5/14 23:35:05   来源:

问题 A: Linear Cellular Automata

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>
#define ll long long  
using namespace std;
int a[66], b[66], p[66];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        memset(a, 0, sizeof(a));
        memset(b, 0,sizeof(b));
        for(int i=0; i<10; i++)  cin>>p[i];
        a[20] = b[20] = 1;
        for(int i=0; i<50; i++) {
            for(int j=1; j<=40; j++) {
                if(a[j]==0)  putchar(' ');
                else if(a[j]==1)  putchar('.');
                else if(a[j]==2)  putchar('x');
                else if(a[j]==3)  putchar('W');
                b[j] = p[a[j-1] + a[j] + a[j+1]];
            }
            cout<<endl;
            for(int j=1; j<=40; j++)  a[j] = b[j];
        }
        if(t) cout<<endl;;
    }
    return 0;
}

问题 C: Error Correction

在这里插入图片描述
在这里插入图片描述

思路:判断行和列的数和是奇数的个数。
1.如果都是0,那么ok
2.如果都是1,那么可以修改一个,使得ok,用一个变量记录数和是奇数所在的行,用一个变量记录数和是奇数所在的列。 最后输出。
3.其他情况都是Corrupt。

#include <bits/stdc++.h>
#define ll long long  
using namespace std;

int main()
{
    int a;
    while(scanf("%d",&a)!=EOF&&a!=0)
    {
        int b[101][101];
        int c[1010],d[1010];
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        for(int i=0; i<a; i++)
        {
            for(int j=0; j<a; j++)
            {
                scanf("%d",&b[i][j]);
                c[i]=b[i][j]+c[i];
            }
        }
        for(int i=0; i<a; i++)
            for(int j=0; j<a; j++)  d[i]+=b[j][i];
        int k=0,kk=0,end=0,x,y;
        for(int i=0; i<a; i++)
        {
            if(c[i]%2==1)
            {
                k++;
                x=i;
            }
            if(d[i]%2==1)
            {
                kk++;
                y=i;
            }
            if(k==2||kk==2)
            {
                printf("Corrupt\n");
                end=1;
                break;
            }
        }
        if(k==0&&kk==0)  printf("OK\n");
        if(k==1&&kk==1)  printf("Change bit (%d,%d)\n",x+1,y+1);
    }
    return 0;
}

问题 E: Soundex

在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>
#define ll long long  
using namespace std;
char last,t,str[66];
int l,arr[66];
 
void init() {
    arr[0] = 0;  // A
    arr[1] = 1;  // B
    arr[2] = 2;  // C
    arr[3] = 3;  // D
    arr[4] = 0;  // E
    arr[5] = 1;  // F
    arr[6] = 2;  // G
    arr[7] = 0;  // H
    arr[8] = 0;  // I
    arr[9] = 2;  // J
    arr[10] = 2; // K
    arr[11] = 4; // L
    arr[12] = 5; // M
    arr[13] = 5; // N
    arr[14] = 0; // O
    arr[15] = 1; // P
    arr[16] = 2; // Q
    arr[17] = 6; // R
    arr[18] = 2; // S
    arr[19] = 3; // T
    arr[20] = 0; // U
    arr[21] = 1; // V
    arr[22] = 0; // W
    arr[23] = 2; // X
    arr[24] = 0; // Y
    arr[25] = 2; // Z
}

int main()
{
    init();
    while(scanf("%s", str) != EOF)
	{
        l = strlen(str);
        last = 0;
        for(int i=0; i<l; i++)
		{
            if(arr[str[i]-'A'] != 0 && arr[str[i]-'A'] != last) 
                printf("%d", (last = arr[str[i]-'A']));
            else  last = arr[str[i]-'A'];
        }
        cout<<endl;
    }
    return 0;
}

问题 F: Antiarithmetic

在这里插入图片描述
在这里插入图片描述

先考虑前后两项,保证中项在前两项之间。算式中的中项有可能是小数,用double o 和 int t,判断o-t?=0,来保证中项为整数。

#include <bits/stdc++.h>
#define ll long long  
using namespace std;

int n,x,l,a[10100];
char m;
double o;

int xc(void) {
    for(int i=0; i<n; i++){
        for(int j=n-1; j>i; j--) {
            o = (i+j)/2.0;
            l = (i+j)/2;
            if(o-l!=0)  continue;
            if(a[i]<a[l]&&a[l]<a[j])  return 1;
        }
    }
    return -1;
}

int main() {
    while(cin>>n && n) {
        cin>>m;
        memset(a,0,sizeof(a));
        for(int i=0; i<n; i++) {
            cin>>x;
            a[x]=i;
        }
        if(xc()==1)  cout<<"no"<<endl;
        else   cout<<"yes"<<endl;
    }
 }

问题 G: Only I did it!

在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>
#define ll long long  
using namespace std;
int T,m,a[6][10010];

int main()
{
	while(~scanf("%d",&T))
	for (int t=1; t<=T; ++ t) {
		memset(a, 0, sizeof(a));
		for(int i=0; i<3; ++ i) {
			scanf("%d",&a[i][0]);
			for(int j=a[i][0]; j>0; --j) {
				scanf("%d",&m);
				a[i][m] = 1;
			}
		}
		
		for(int i=1; i<10001; ++ i)
			if(a[0][i]+a[1][i]+a[2][i] > 1) {
				a[0][0] -= a[0][i]; a[0][i] = 0;
				a[1][0] -= a[1][i]; a[1][i] = 0;
				a[2][0] -= a[2][i]; a[2][i] = 0;
			}
		
		int max=0;
		for(int i=0; i<3; ++i)
			if(max<a[i][0])	max=a[i][0];
		
		printf("Case #%d:\n",t);
		for(int i=0; i<3; ++i)
			if(a[i][0] == max) {
				printf("%d %d",i+1,a[i][0]);
				for(int j=1; j<10001; ++ j)
					if(a[i][j])	printf(" %d",j);
				cout<<endl;
			}
	}
    return 0;
}

问题 H: Square Numbers

在这里插入图片描述
在这里插入图片描述

代码不小心整没了… 懒得打了

问题 I: 面积

在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
int n,a[10010];
ll sum;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)  cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1; i<=n; i++)  sum += i*a[i];

	printf("%lld",sum);
    return 0;
}

问题 J: 分数

在这里插入图片描述
在这里插入图片描述

代码不小心整没了… 懒得打了

问题 L: 排队

在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>
#define ll long long  
#define MAXN 1000010
using namespace std;

int n,d[MAXN],t[MAXN],rg[MAXN];
ll ct;
 
int AC(int v,int l,int r) {
    while(l<=r) {
        int mid=(l+r)>>1;
        if(mid>=n) return mid;
        if(t[mid]>v)  r=mid-1;
        else if(t[mid]==v) {
		    if(!rg[mid]) return mid;
			else return n;
		}
        else if(t[mid]<v)  l=mid+1;
    }
}

int getmin(){
    mempcpy(t,d,n*sizeof(int));
    sort(t,t+n);
    for(int i=0;i <n; ++i) rg[i]=(t[i]==d[i]);
    int ans=0,p=0;
    ct=0;
    while(1) {
        while(p<n&&rg[p])  p++;
        if(p>=n)  break;
        int q=AC(d[p],p+1,n);
        if(q>=n)  break;
        rg[q]=true;
        if(d[q]==t[p]) rg[p]=true;
        swap(d[p],d[q]);
        ans++;
    }
    return ans;
}

int main() {
    while(scanf("%d",&n)==1) {
        for(int i=0; i<n; ++i)  scanf("%d",&d[i]);
        printf("%d\n",getmin());
    }
    return 0;
}