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,a%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("%s",s+1);
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("%s\n",t+1);
}
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]%=mod;
scanf("%s",s+1);
}
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],ans%=mod,cnt=1;
}
ans=ans*f[cnt],ans%=mod;
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("%d ",i);
puts("");cout<<cnt<<endl;
for(int i=1;i<=cnt;++i)printf("%lld %lld\n",e[i].x,e[i].y);
}
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("%d",&a[i][j]);
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("%.12lf\n",dp[0]);
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("%d",&T);
while(T--)
{
cin>>l>>r;
mem(dp,-1);
ll ans=solve();
printf("%lld\n",ans);
}
return 0;
}
Comments NOTHING