Codeforces Round #597(Div.2) 解题报告

发布于 2019-11-04  22 次阅读



A.Good ol' Numbers Coloring
题干真长
NOIP2017小凯的疑惑的某一引理,直接看$a$和$b$的最小公倍数,over
这个定理名字也挺好玩的...Chicken McNugget Theorem

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int gcd(int a,int b){return b==0?a:gcd(b,
int main()
{
    int T;cin>>T;
    while(T--)
    {
        int a,b;
        cin>>a>>b;
        int g=gcd(a,b);
        if(g==1)puts("Finite");
        else puts("Infinite");
    }
    return 0;
}

B.Restricted RPS
不知道这题为什么把一些大佬卡住了
这题就直接先贪心选,然后剩下的空位随便补就行
(我居然一开始把&&写成了&......)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int a,b,c;
char s[150];
char t[150];
int cnt;
int main()
{
    int T;cin>>T;
    while(T--)
    {
        memset(t,0,sizeof t);
        cnt=0;
        cin>>n;
        cin>>a>>b>>c;
        scanf(
        for(int i=1;i<=n;++i)
        {
            if(s[i]=='P'&&c)
            {
                c--;
                t[i]='S';
                cnt++;
            }
            if(s[i]=='R'&&b)
            {
                b--;
                t[i]='P';
                cnt++;
            }
            if(s[i]=='S'&&a)
            {
                a--;
                t[i]='R';
                cnt++;
            }
        }
        if(cnt<(n+1)/2){puts("NO");continue;}
        for(int i=1;i<=n;++i)
        {
            if(t[i]==0&&c)
            {
                c--;
                t[i]='S';
            }
            if(t[i]==0&&b)
            {
                b--;
                t[i]='P';
            }
            if(t[i]==0&&a)
            {
                a--;
                t[i]='R';
            }
        }
        printf("YES\n");
        printf(
    }
    return 0;
}

C.Constanze's Machine
可以看出与斐波那契有关......然后瞎搞一波
Code by ZXyang

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=300050;
const ll mod=1e9+7;
int f[N];char s[N];
void Init()
{
    f[1]=f[0]=1;
    for(int i=2;i<=100000;++i)f[i]=f[i-1]+f[i-2],f[i
    scanf(
}
ll ans;
int main()
{
    Init();
    int n=strlen(s+1),cnt=1;
    ans=1;
    for(int i=1;i<=n;++i)
    {
        if((s[i]=='u'||s[i]=='n')&&s[i]==s[i-1])++cnt;
        else if(s[i]=='m'||s[i]=='w')ans=0;
        else ans=ans*f[cnt],an
    }
    ans=ans*f[cnt],an
    cout<<ans<<endl;
    return 0;
}

D.Shichikuji and Power Grid
Prim+方案输出......裸的
Code by ZXyang

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
const ll inf=0x3f3f3f3f3f3f;
const ll INF=~(1LL<<63);
const int N=2050;
struct ansedges
{
    ll x,y;
}e[N];
ll yes[N],x[N],y[N],c[N],k[N];
ll a[N][N],cnt;
ll d[N],fangwen[N],n,PT[N];
inline ll getprim()
{
    mem(d,0x3f);
    d[0]=0;ll ret=0;fangwen[0]=1;
    for(int i=1;i<=n;++i)d[i]=min(d[i],a[0][i]);
    for(int KASE=1;KASE<=n;++KASE){
        ll minn=INF,nowpos=0;
        for(int i=0;i<=n;++i){
			if(fangwen[i]==false&&minn>d[i]){
            	minn=d[i];
            	nowpos=i;
        	}
		}
        fangwen[nowpos]=1;
        ret+=minn;
        if(nowpos&&PT[nowpos])e[++cnt]={nowpos,PT[nowpos]};
        else yes[nowpos]=yes[max(nowpos,PT[nowpos])]=1;
        for(int i=0;i<=n;++i){
            if(nowpos!=i&&d[i]>a[nowpos][i]&&fangwen[i]==false){
                d[i]=a[nowpos][i];
                PT[i]=nowpos;
            }
        }
    }
    return ret;
}
int main()
{
    int T;T=1;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;++i)cin>>x[i]>>y[i];
        for(int i=1;i<=n;++i)cin>>c[i];
        for(int i=1;i<=n;++i)cin>>k[i];
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            	if(i!=j)a[i][j]=a[j][i]=(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]));
        for(int i=1;i<=n;++i)a[0][i]=a[i][0]=c[i];
        ll ans1=getprim();ll ans2=0;
        for(int i=1;i<=n;++i)if(yes[i])++ans2;
        cout<<ans1<<endl;
		cout<<ans2<<endl;
        for(int i=1;i<=n;++i)if(yes[i])printf(
        puts("");cout<<cnt<<endl;
        for(int i=1;i<=cnt;++i)printf(
    }
    return 0;
}

E.Hyakugoku and Ladders
神奇的期望dp......
其实道理很简单,我们倒着dp。首先为了简化,我们把方格图弄成序列,反正路径都是那些。
设$dp[i]$表示到$i$的最小期望,然后$up[i]$表示从某个点爬梯子到$i$,之后的转移就很简单了,$dp[0]$就是我们需要的答案。
转移的话,到达i这个点有两种,一种是爬梯子到他,另一种是直接掷骰子到他,于是dp方程就出来了:$dp[i]=1+min(dp[i+k],dp[up[i+k]])$,其中$k$表示掷得的点数。
不过对于终点附近那6个格子,由于题干条件,会出现不能走的情况,我们就需要记录一下,再乘以当前的$dp[i]$就行。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const double inf=9999999999999LL;
const double p=1.0/6.0;
int a[15][15];
int n=10;
double dp[250];
int up[250];
inline int id(int x,int y)
{
    return (9-x)*n+((x&1)?y:9-y);
}
int main()
{
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            scanf(
    int x=9,y=0,d=1;
    for(int i=0;i<100;++i)
    {
        up[i]=id(x-a[x][y],y);
        if(y+d<0||y+d>=10)d=-d,x--;
        else y+=d;
    }
    dp[99]=0;
    for(int i=98;i>=0;--i)
    {
        dp[i]=1.0;
        int c=6;
        for(int k=1;k<=6;++k)
        {
            if(i+k>=100)break;
            dp[i]+=min(dp[i+k],dp[up[i+k]])/6.0;
            c--;
        }
        dp[i]=6.0*dp[i]/(6-c);
    }
    printf(
    return 0;
}

F.Daniel and Spring Cleaning
数位dp...怎么这么多dp呀
随便搞搞就能发现,$a+b=a \oplus b$的条件就是$a$与$b$二进制的位数相等(或者$b$的位数小于等于$a$),并且$a$与$b$在相同位上不同时有$1$,这就转化成了一道组合计数的题目。
然后就数位dp瞎搞了......

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
int n;
ll dp[40][2][2][2][2];
int L[40],R[40];
ll l,r;
ll dfs(int pos,bool lessL,bool biggerL,bool lessR,bool biggerR)
{
    if(pos==31)return 1;
    ll &now=dp[pos][lessL][biggerL][lessR][biggerR];
    if(~now)return now;
    now=0;
    int upl=lessL?1:R[pos];
    int lowl=biggerL?0:L[pos];
    int upr=lessR?1:R[pos];
    int lowr=biggerR?0:L[pos];
    for(int i=lowr;i<=upr;++i)
    {
        for(int j=lowl;j<=upl;++j)
        {
            if(i&j)continue;
            now+=dfs(pos+1,lessL||j!=R[pos],biggerL||j!=L[pos],lessR||i!=R[pos],biggerR||i!=L[pos]);
        }
    }
    return now;
}
ll solve()
{
    mem(L,-1);mem(R,-1);
    for(int i=0;i<31;++i)
    {
        L[30-i]=(l>>i)&1;
        R[30-i]=(r>>i)&1;
    }
    ll ret=dfs(0,0,0,0,0);
    return ret;
}
int main()
{
    int T;scanf(
    while(T--)
    {
        cin>>l>>r;
        mem(dp,-1);
        ll ans=solve();
        printf(
    }
    return 0;
}