Educational Codeforces Round 83 (Rated for Div. 2)A--C

时间:2020-03-11 liyexin 人气:0

　　　　题意：给出一个边数为n的等边多边形，问是否可以变成m的等边多边形。条件是同一个中心，共用原顶点。

　　　解析：直接n%m==0即可，这样就是平分了。签到题没得说了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=1e4;
int pr[maxn];
int find(int x)
{
    if(x!=pr[x])
        return pr[x]=find(pr[x]);
        return x;
}
void join(int x1,int x2)
{
    int f1=find(x1),f2=find(x2);
    if(f1!=f2)
    {
        pr[f1]=f2;
    }
    return ;
}
int main()
{
    int    t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        if(n%m==0)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

　　　　题意：把给定数组任意排列，保证i<j时，j-a[j]!=i-a[i]。输出任意一组答案。

　　　　解析：sort一下从大到小排列即可。看数据的话，暴力也是可以的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
int a[105];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];    
        while(1)
        {
            int ok=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=i+1;j<=n;j++)
                {
                    if((j-a[j])==(i-a[i]))
                    {
                        ok=1;break;
                    }
                }
                if(ok)
                    break;
            }
            if(!ok)
                break;
            for(int i=1;i<=n;i++)
            {
                for(int j=i+1;j<=n;j++)
                {
                    if((j-a[j])==(i-a[i]))
                    {
                        swap(a[i],a[j]);
                    }
                }
            }
        }
        for(int i=1;i<n;i++)
            cout<<a[i]<<" ";
            cout<<a[n]<<endl;
    }    

}

　　　　题意：给你一个个数为n的数组a[],判断是否可以由相同大小的全0数组v[]变换而来。

　　　　　　变换规则：

　　　　　　　　　　　　1.在第i次操作时，你可以给数组v任意位置的值加上k^i

　　　　　　　　　　　　2.在第i次什么也不做。

　　　　解析：这其实就是一个进制的题。对于任意一个a【i】假设k进制对其有n位：a[i]= x0* k^0 +x1* k^1 +x2* k^2 +……+x(n-1)* k^n-1

　　　　　　　而这个题对于k^i的i，是不断递增的，即每个i只能出现一次。所以我们只要知道每个k^i的系数，大于1，就是NO了。

　　　　　　　举个例子：二进制，k=2　　

　　　　　　　　　　　　　　　　　 5　　6

　　　　　　　5的二进制表示为101，2为110，101

　　　　　　　　　　　　　　　　　　　　　　110　　　　可以看出，2^2那里出现了两次，肯定不服题意了。

　　　　　　　这里用vis[]来记录各个k^i的出现次数，记住vis是与实际转化的k进制数方向是相反的。vis[]+=a[i]%k，这个a[i]%k，就是系数，即次数。最后注意一下vis[]开的大些

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=40;
const int maxn2=100;
ll a[maxn];
int vis[maxn2];
int t;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
            scanf("%lld",&a[i]);
        memset(vis,0,sizeof(vis));
        int ok=0;
        for(int i=0;i<n;i++)
        {
            int tot=0;
            while(a[i])
            {
                tot++;
                vis[tot]+=a[i]%k;
                a[i]=a[i]/k;
                if(vis[tot]>1)
                {
                    ok=1;break;
                }
            }
            if(ok)
                break;
        }
        if(!ok)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

加载全部内容