近几年ACM/ICPC区域赛铜牌题(1) [Cloned]

近几年ACM/ICPC区域赛铜牌题(1) [Cloned]

A-String

B-Little Tiger vs. Deep Monkey

C-Hard Code

题意：

给你一个字符串，n，m，输出n行，每行m个字符（字符串分割）。

#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int n,m;
int main()
{
   
    cin>>t;
    while(t--)
    {
   
        cin>>n>>m;
        cin>>s;
        for(int i=0;i<n;i++)
        {
   
            for(int j=0;j<m;j++)
            {
   
                printf("%c",s[i*m+j]);
            }
            printf("\n");
        }
    }
    return 0;
}

D-Wall Painting

题意：

给了n个包，第k天混合任意k个包，得到${（}_k^n）$种不同方案，包混合后的值为混合的k个包的异或和，第k天的所有方案的异或和求和

solution：

将包的值进行二进制分解，由异或和性质可知相同为0，相异为1，当前二进制为如果要对答案产生贡献，那么当前二进制所选取1的个数必须为奇数，0的个数为剩余数量，两者之和必须大于等于k，直接进行组合数求解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const ll mo=1e6+3;
ll C(ll n,ll m){
   
    static ll M=0,inv[10005],mul[10005],invMul[10005];
    while(M<=n){
   
        if(M){
   
            inv[M]=M==1?1:(mo-mo/M)*inv[mo%M]%mo;
            mul[M]=mul[M-1]*M%mo;
            invMul[M]=invMul[M-1]*inv[M]%mo;
        }
        else mul[M]=1,invMul[M]=1;
        M++;
    }
    return mul[n]*invMul[m]%mo*invMul[n-m]%mo;
}
int n;
ll a[1005];
int x[70];
ll res[1005];
int main()
{
   
    while(scanf("%d",&n)!=EOF)
    {
   
        for(int i=1;i<=n;i++)
        {
   
            scanf("%lld",&a[i]);
            res[i]=0;
        }
        memset(x,0,sizeof(x));
        int cnt=0;
        while(true)
        {
   
            bool flag=true;
            for(int i=1;i<=n;i++)
            {
   
                if(a[i]%2==1)
                    x[cnt]++;
                a[i]/=2;
                if(a[i])flag=false;
            }
            if(flag)break;
            cnt++;
        }
        for(int i=1;i<=n;i++)
        {
   
            for(int j=0;j<=cnt;j++)
            {
   
                ll add=(1ll<<j)%mo;
                for(int k=1;k<=i;k+=2)
                {
   
                    if(x[j]<k||n-x[j]<i-k)continue;
                    res[i]=(res[i]+1ll*add*C(x[j],k)%mo*C(n-x[j],i-k)%mo)%mo;
                }
            }
        }
        printf("%lld",res[1]);
        for(int i=2;i<=n;i++)
            printf(" %lld",res[i]);
        printf("\n");
    }
    return 0;
}

E-Ball

F-Zhuge Liang’s Password

题意：

给了两张n行n列的卡片，对其中一张卡片进行0，90，180，270度旋转，两张卡片重叠后，相同的地方最多有几处

solution：

暴力模拟。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n;
int a[35][35],b[35][35];
void zhuan()
{
   
    int tem[35][35];
    for(int i=0;i<n;i++)
    {
   
        for(int j=0;j<n;j++)
        {
   
            tem[i][j]=a[n-j-1][i];
        }
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        a[i][j]=tem[i][j];
}
int main()
{
   
    while(~scanf("%d",&n))
    {
   
        if(n==0)break;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            scanf("%d",&a[i][j]);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            scanf("%d",&b[i][j]);
            zhuan();
        int res=0;
        for(int i=0;i<4;i++)
        {
   
            if(i!=0)
                zhuan();
            int cnt=0;
            for(int j=0;j<n;j++)
            {
   
                for(int k=0;k<n;k++)
                    if(a[j][k]==b[j][k])cnt++;
            }
            res=max(res,cnt);
        }
        printf("%d\n",res);
    }
    return 0;
}

G-Stealing Harry Potter’s Precious

题意：

给了一个n，m的二维矩阵，@为起点，要通过给定的k个点，问通过这k个点的最小距离。不能完全通过输出-1。（#不能走，.可以走）

solution：

将起点和给定的k个点都求以该点为起点到其他地方的最短距离。之后跑一边dfs，求不同的顺序下最短距离是多少。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,m,k;
int sx[10],sy[10];
char tu[105][105];
int d[10][105][105];
int dx[]={
   0,0,1,-1},dy[]={
   1,-1,0,0};
int vis[10];
int minn;
void bfs()
{
   
    memset(d,INF,sizeof(d));
    for(int i=0;i<=k;i++)
    {
   
        queue<P> que;
        d[i][sx[i]][sy[i]]=0;
        que.push(P(sx[i],sy[i]));
        while(!que.empty())
        {
   
            P p=que.front();que.pop();
            for(int j=0;j<4;j++)
            {
   
                int x=p.first+dx[j],y=p.second+dy[j];
                if(x<1||x>n||y<1||y>m)continue;
                if(tu[x][y]=='#'||d[i][x][y]!=INF)continue;
                d[i][x][y]=d[i][p.first][p.second]+1;
                que.push(P(x,y));
            }
        }
    }
}
void dfs(int fa,int s,int c)
{
   
    if(c==k){
   
        minn=min(minn,s);
        return;
    }
    for(int i=0;i<=k;i++)
    {
   
        if(vis[i]||d[fa][sx[i]][sy[i]]==INF)continue;
        vis[i]=1;
        dfs(i,s+d[fa][sx[i]][sy[i]],c+1);
        vis[i]=0;
    }
}
int main()
{
   
    while(~scanf("%d%d",&n,&m))
    {
   
        if(n==0&&m==0)break;
        for(int i=1;i<=n;i++)
            cin>>tu[i]+1;
        for(int i=1;i<=n;i++)
        {
   
            for(int j=1;j<=m;j++)
            {
   
                if(tu[i][j]=='@')
                    sx[0]=i,sy[0]=j;
            }
        }
        scanf("%d",&k);
        minn=INF;
        for(int i=1;i<=k;i++)
            scanf("%d%d",&sx[i],&sy[i]);
        bfs();
        memset(vis,0,sizeof(vis));
        vis[0]=1;
        dfs(0,0,0);
        if(minn==INF)
            printf("-1\n");
        else
            printf("%d\n",minn);
    }
    return 0;
}

H-Lights Against Dudely

I-Fibonacci Tree

J-Little Zu Chongzhi’s Triangles

K-How Many Maos Does the Guanxi Worth

L-GTY’s gay friends

M-The E-pang Palace

N-Dire Wolf

O-Happy Matt Friends

P-Intersection

Q-K.Bro Sorting

题意：

给了一个数组，问要进行多少伦冒泡排序

solution：

判断当前数是否比后面的某个数大就可以了。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int t,n,a[1000005];
int main()
{
   
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
   
        scanf("%d",&n);
        for(int j=0;j<n;j++)
            scanf("%d",&a[j]);
        int ans=0,minn=INF;
        for(int j=n-1;j>=0;j--)
        {
   
            if(a[j]>minn)ans++;
            minn=min(minn,a[j]);
        }
        printf("Case #%d: %d\n",i,ans);
    }
    return 0;
}

R-A Curious Matt

题意：

给了n个位置，以及走到当前位置时的时间，求最大速度。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
struct node
{
   
    int t,x;
    bool operator <(node b)
    {
   
        return t<b.t;
    }
}a[10010];
int main(){
   
    int t;scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
   
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d%d",&a[i].t,&a[i].x);
        sort(a+1,a+1+n);
        double ans=0;
        for(int i=2;i<=n;i++)
        {
   
            ans=max(ans,abs(a[i].x-a[i-1].x)*1.0/(a[i].t-a[i-1].t));
        }
        printf("Case #%d: %.2f\n",cas,ans);
    }
    return 0;
}

S-Osu!

T-Hatsune Miku

U-Galaxy