模拟赛
困
T1 琪露诺的算数游戏
小·大模拟，注意：
- 负数向下取整可用右移或
floor。 - 优先级，注意有标记和无标记是不同的，可以用
map初始化。 - 解牌除标记后直接跳下一个人。
- 区分 \(D\) 和 \(DOUBLE\)。
大模拟打的太少了
code
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int n,m,k,now,st,p,fl=1;
string d[N];
bool dou;
map<char,int> mp[2]={{{'C',1},{'A',2},{'B',3},{'D',4},{'E',5}},{{'D',1},{'B',2},{'A',3},{'C',4},{'E',5}}};
//注意优先级
struct P
{
string name;
string c[3];
} a[35];
int cal(int x,string c)
{
int len=c.length(),tmp=0;
if(len==2) tmp=c[1]-48;
else tmp=(c[1]-48)*10+c[2]-48;
if(c[0]=='A') return x+tmp;
else if(c[0]=='B') return x-tmp;
else if(c[0]=='C') return x*2;
else if(c[0]=='D'&&c[1]!='O') return x>>=1;//和 DOUBLE 区分，注意向下取整
else if(c[0]=='E') return tmp;
else return 10000000;// 单独考虑解牌，这里不计
}
bool jd(int i)//暴力搞
{
for(int j=0;j<3;j++) if(a[i].c[j]=="PASS")
{
cout<<a[i].name<<" used "<<a[i].c[j]<<",now p="<<p<<".\n";
a[i].c[j]=d[++now]; return 1;
}
for(int j=0;j<3;j++) if(a[i].c[j]=="TURN")
{
cout<<a[i].name<<" used "<<a[i].c[j]<<",now p="<<p<<".\n";
a[i].c[j]=d[++now];fl*=-1; return 1;
}
for(int j=0;j<3;j++) if(a[i].c[j]=="DOUBLE")
{
cout<<a[i].name<<" used "<<a[i].c[j]<<",now p="<<p<<".\n";
a[i].c[j]=d[++now]; dou=1; return 1;
}
return 0;
}
pair<int,int> work(int i,bool op)
{
int tm,id;
if(op==0)
{
tm=-1e9,id=-1;
for(int j=0;j<3;j++)
{
int tmp=cal(p,a[i].c[j]);
if(tmp>99) continue;
else if(tmp>tm) tm=tmp,id=j;//较大的
else if(tmp==tm)
{
if(mp[op][a[i].c[id][0]]>mp[op][a[i].c[j][0]]) id=j;
}
}
}
else
{
tm=1e9,id=-1;
for(int j=0;j<3;j++)
{
int tmp=cal(p,a[i].c[j]);
if(tmp>99) continue;
else if(tmp<tm) tm=tmp,id=j;//较小的
else if(tmp==tm)
{
if(mp[op][a[i].c[id][0]]>mp[op][a[i].c[j][0]]) id=j;
}
}
}
return make_pair(tm,id);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
cin>>a[i].name>>a[i].c[0]>>a[i].c[1]>>a[i].c[2];
}
for(int i=1;i<=k;i++) cin>>d[i];
st=1;
for(int g=1;g<=m;g++)
{
printf("Round %d:\n",g);
p=0; fl=1;//重置
for(int i=st;;i+=fl)
{
if(i==n+1) i=1;
if(i==0) i=n;
if(dou)
{
if(!jd(i))//先判解牌
{
dou=0;//没有解牌，消除标记
pair<int,int> pii=work(i,1);
int id=pii.second,tm=pii.first;
if(id!=-1)
{
p=tm;
cout<<a[i].name<<" used "<<a[i].c[id]<<",now p="<<p<<".\n";
a[i].c[id]=d[++now];
}
else
{
if(jd(i)) continue;
cout<<a[i].name<<" lost the game.\n";
for(int j=0;j<3;j++) a[i].c[j]=d[++now];
st=i; break;
}
}
else continue;//注意直接跳
}
pair<int,int> pii=work(i,0);
int id=pii.second,tm=pii.first;
if(id!=-1)
{
p=tm;
cout<<a[i].name<<" used "<<a[i].c[id]<<",now p="<<p<<".\n";
a[i].c[id]=d[++now];
}
else
{
if(jd(i)) continue;//判解牌
cout<<a[i].name<<" lost the game.\n";
for(int j=0;j<3;j++) a[i].c[j]=d[++now];
st=i; break;
}
}
}
return 0;
}
T2 Minesweeper 1D
显然 dp，但是每一位都会对后一位产生影响，我们可以设计状态来限制后一位。
\(f_{i,0/1/2}\) 表示第 \(i,i+1\) 都没雷，第 \(i\) 没雷第 \(i+1\) 有雷，第 \(i\) 位有雷第 \(i+1\) 未知。
这三种状态其实分别对应了题面中 \(0,1,*\)，前两种会对后一位产生影响但本位上一定没有，第三种不会对后面有影响，但是本位上一定有。
因此 我们用完全按题面去设计状态，考虑怎样的状态能进行我们想要的转移，不重不漏，不然可能不太好想。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5,mod = 1e9+7;
#define LL long long
int n;
char s[N];
LL f[N][3];
int main()
{
scanf("%s",s+1); n=strlen(s+1);
f[0][0]=f[0][1]=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='0') f[i][0]=f[i-1][0];
else if(s[i]=='2') f[i][1]=f[i-1][2];
else if(s[i]=='*') f[i][2]=f[i-1][2]+f[i-1][1],f[i][2]%=mod;
else if(s[i]=='1') f[i][1]=f[i-1][0],f[i][0]=f[i-1][2];
else f[i][0]=f[i][1]=(f[i-1][2]+f[i-1][0])%mod,f[i][2]=(f[i-1][1]+f[i-1][2])%mod;
}
printf("%lld\n",(f[n][0]+f[n][2])%mod);
return 0;
}
还可以卡卡空间，因为转移都只涉及上一层，所以第一维可以压掉。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5,mod = 1e9+7;
int n,f[4];
char s[N];
int main()
{
scanf("%s",s+1); n=strlen(s+1);
f[0]=f[1]=1;
for(register int i=1;i<=n;++i)
{
if(s[i]=='0') f[0]=f[0],f[1]=f[2]=0;
else if(s[i]=='2') f[1]=f[2],f[2]=f[0]=0;
else if(s[i]=='*') f[2]=(1ll*f[2]+f[1])%mod,f[1]=f[0]=0;
else if(s[i]=='1') f[1]=f[0],f[0]=f[2],f[2]=0;
else f[3]=f[1],f[0]=f[1]=(1ll*f[2]+f[0])%mod,f[2]=(1ll*f[3]+f[2])%mod;
}
printf("%d\n",(1ll*f[0]+f[2])%mod);
return 0;
}
T3 小凯的疑惑
链接题目与本题不完全一样！！！以题目描述为准！！！
题目描述
Description
已知两个数 x,y 求有多少个正整数不能被 a×x+b×y,a≥0,b≥0 表示
Input Format
一行两个整数表示 x,y
Output Format
一行一个整数表示答案,若有无穷个数无法被表示,输出-1
Sample
样例输入
2 3
样例输出
1
Hint
对于全部测试点,1≤x,y≤108
子任务 1(10 分):1≤x,y≤1000
子任务 2(20 分):∣y−x∣=1
子任务 3(30 分):x,y 互质
子任务 4(40 分):无特殊性质
\(ax+by\) 的值一定是 \(gcd(x,y)\) 的倍数,所以如果 \(gcd(x,y) \ne 1\) 的话,一定是无穷多个。
所以我们只需要考虑 \(gcd(x,y) = 1\) 的情况。
不妨设 \(x\) 为基准,那么假如只有 \(x\),每两个 \(x\) 的倍数之间会有 \(x-1\) 个数的空隙。
我们的目的就是用 \(y\) 去填满这 \(x-1\) 个空隙.也就是令 \(i \times y \mod x\) 等于 \([x+1,2x-1]\)。
最终显然是能填满的，否则一定会出现循环节，也就不满足 \(gdc(x,y)=1\) 了。
一旦第一次填满后，后面可以通过 \(x\) 的加减保证每一个数都能覆盖到。
所以我们要求的就是在第一次之前有多少个数不能被覆盖。
我们可以枚举位置，计算每个位置第一次是在哪一块被覆盖到，这个位置的贡献就是没被覆盖到的块数。
也就是 $$\sum_{i=1}^{x-1}{\lfloor{\frac{i \times y}{x}}\rfloor}$$
然后开始化简：
\[\sum_{i=1}^{x-1}{\lfloor{\frac{i \times y - (i \times y) \mod x}{x}}\rfloor} \]\[\because gcd(x,y)=1,\quad \therefore gcd(i \times x)=1 \]\[\sum_{i=1}^{x-1}{\lfloor{\frac{i \times y - 1}{x}}\rfloor} \]\[\frac{(x-1)(y-1)}{2} \]\(O(1)\) 即可。
code
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
scanf("%d%d",&a,&b);
if(__gcd(a,b)!=1) printf("-1\n");
else printf("%lld\n",1ll*(a-1)*(b-1)/2);
return 0;
}
T4 春节十二响
一条链上的不能在同一个集合，也就是每一层分一堆。
两条链合并时一定是大的和大的合并，小的和小的合并最优。
比较简单，赛时 \(\mathbb{T}\) 了，学会启发式合并。
启发式合并：每次把小的合并到大的里面，减少合并复杂度。
名字怎么这么高级
开优先队列，将儿子合并到父亲里，，启发式合并就是直接交换容器然后合并。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
#define LL long long
int n,a[N],tmp[N],tot,cnt,head[N];
struct E {int u,v;} e[N<<1];
void add(int u,int v) {e[++tot]={head[u],v}; head[u]=tot;}
LL ans;
priority_queue<int> q[N];
void dfs(int u,int fa)
{
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u); cnt=0;
if(q[u].size()<q[v].size()) swap(q[u],q[v]);//!!!!!!!!!!!!!!!
while(!q[u].empty()&&!q[v].empty()) tmp[++cnt]=max(q[u].top(),q[v].top()),q[u].pop(),q[v].pop();
for(int j=1;j<=cnt;j++) q[u].push(tmp[j]);
}
q[u].push(a[u]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=2;i<=n;i++)
{
int x; scanf("%d",&x);
add(i,x); add(x,i);
}
dfs(1,0);
for(;!q[1].empty();q[1].pop()) ans+=q[1].top();
printf("%lld\n",ans);
return 0;
}