这一场前四题的题目难度还可以 下面为前四题的简易题解
A:Gennady the Dentist
题意：
有N(N<=4000)个孩子去看病 编号从1~n排成一列 每个孩子有三个属性v[i],d[i],p[i]表
v[i]表示孩子哭声的大小
d[i]表示孩子尖叫声的大小
p[i]表示孩子的忍耐度
每次一个孩子进去看病 发出v的哭声 后面排队的第I个孩子受到v-i+1的惊吓 忍耐度减少v-i+1
如果第J个孩子忍耐度<0 就会发出尖叫并离开队伍 对j之后的所有孩子造成d的惊吓
问最后有多少孩子可以看病
题解：
按照题意模拟即可 有两个trick
1：忍耐度有可能超过INT 需要使用LL
2：发出V的哭声时 先是对队伍中所有孩子造成相应影响 接下来在考虑离开队伍造成的位置变化
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
int n;
LL a[5005],b[5005],c[5005];
int dq,now;
vector<int> v;
const int INF=19950920;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%I64d%I64d%I64d",&a[i],&b[i],&c[i]);
dq=1;
while (dq<=n)
{
while (dq<=n&&c[dq]<0) dq++;
if (dq>n) break;
now=a[dq];
v.push_back(dq);
for (int i=dq+1;i<=n;++i)
{
if (c[i]>=0)
{
c[i]-=now;
now--;
if (now==0) break;
}
}
for (int i=dq+1;i<=n;++i)
{
if (c[i]>=0) continue;
if (c[i]==-INF) continue;
c[i]=-INF;
for (int j=i+1;j<=n;++j)
{
if (c[j]>=0) c[j]-=b[i];
}
}
dq++;
}
printf("%d\n",v.size());
for (int i=0;i<v.size();++i) printf("%d ",v[i]);
return 0;
}
B:Phillip and Trains
题意：
给定一个3*n(n<=100)的方格图,一个人处于最左端要去往最右,格子中有一些长度>=2的地铁,每一秒人与车轮流行动
人：向右走一格 然后选择不动或者向上向下(如果可以)
车：向左走两格
任何时刻人与车不能处于同一格子 问人能不能走到最右
题解：
简单题 f[i][j]表示能否到达(i,j)这个格子
转移：若f[i][j]可达 且当前(i,j+1),(i,j+2),(i,j+3) 没车子 那么f[i][j+1]可达
若f[i][j]可达 且当前(i,j+1),(i-1,j+1),(i-1,j+2),(i-1,j+3)没车子 那么f[i-1][j+1]可达
若f[i][j]可达 且当前(i,j+1),(i+1,j+1),(i+1,j+2),(i+1,j+3)没车子 那么f[i+1][j+1]可达
处理一下最后看f[0][n],f[1][n],f[2][n]能否可达即可
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
int T,n,m;
char s[3][500];
bool dp[3][500],ans;
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
scanf("%s",s[0]);
scanf("%s",s[1]);
scanf("%s",s[2]);
for (int i=n;i<=400;++i) s[0][i]=s[1][i]=s[2][i]='.';
memset(dp,false,sizeof(dp));
if (s[0][0]=='s') dp[0][0]=true;
if (s[1][0]=='s') dp[1][0]=true;
if (s[2][0]=='s') dp[2][0]=true;
for (int j=0;j<n;++j)
for (int i=0;i<3;++i)
{
if (!dp[i][j]) continue;
//zou dao i j+1
//j s
if (s[i][2*j+j+1]!='.') continue;
if ((s[i][2*j+j+1]=='.')&&(s[i][2*j+j+2]=='.')&&(s[i][2*j+j+3]=='.')) dp[i][j+1]=true;
if (i>0)
if ((s[i-1][2*j+j+1]=='.')&&(s[i-1][2*j+j+2]=='.')&&(s[i-1][2*j+j+3]=='.')) dp[i-1][j+1]=true;
if (i<2)
if ((s[i+1][2*j+j+1]=='.')&&(s[i+1][2*j+j+2]=='.')&&(s[i+1][2*j+j+3]=='.')) dp[i+1][j+1]=true;
}
ans=false;
if (dp[0][n-1]) ans=true;
if (dp[1][n-1]) ans=true;
if (dp[2][n-1]) ans=true;
if (ans) printf("YES\n");
else printf("NO\n");
}
return 0;
}
C:Alice, Bob, Oranges and Apples
题意:
你有两个二元组(x1,y1),(x2,y2),每次你可以选择两种操作：
A:(x1,y1),(x2,y2)—>(x1,y1),(x1+x2,y1+y2)
B:(x1,y1),(x2,y2)—>(x1+x2,y1+y2),(x2,y2)
初始为(1,0)和(0,1)现在要求给出一个操作序列 使得达到最终态:x1+x2=n y1+y2=m
(n,m<=1e18)
题解：
很有趣的一道题 首先先来看无解的情况
若gcd(n,m)!=1 则一定无解
我们接下来看有解的情况
考虑一个2$\times$2的矩阵
$((x1,x2),(y1,y2))$
考虑B操作
$((x1,x2),(y1,y2)) \times ((1,0),(1,1)) = ((x1+x2,x2),(y1+y2,y2))$
我们令B=((1,0),(1,1))
考虑A操作
$((x1,x2),(y1,y2)) \times ((1,1),(0,1)) = ((x1,x1+x2),(y1,y1+y2))$
我们令A=((1,1),(0,1))
那么考虑一个函数F
$F(((x1,x2),(y1,y2))) = (y1+y2)/(x1+x2)$
那么考虑一个状态S $F(BS)=(x1+x2+y1+y2)/(x1+x2)=F(s)+1$
所以若$F(BS)=m/n$ $F(s)=(m-n)/n$
所以若$F(AS)=m/n$ $F(s)=m/(n-m)$
这样我们就可以知道对于任意时刻：
-若m>n 那么第一步肯定是B 状态变为(n,m-n)
-若n>m 那么第一部肯定是A 状态变为(n-m,m)
//Latex的矩阵太难打啦！原谅我这个公式写的这么low吧。。用笔写一下就好啦！
这样问题就变成了类似于求GCD得辗转相除 问题就得到完满解决啦
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
LL n,m;
int main()
{
scanf("%I64d%I64d",&n,&m);
if (__gcd(n,m)!=1)
{
printf("Impossible\n");
return 0;
}
while (n!=m)
{
if (n>m)
{
printf("%I64dA",(n-1)/m);
n-=(n-1)/m*m;
}
else
{
printf("%I64dB",(m-1)/n);
m-=(m-1)/n*n;
}
}
return 0;
}
//此问题在具体数学中出现过 见具体数学第121页
D:Lizard Era: Beginning
题意：
有N个任务(N<=25)需要去完成 你有三个伙伴A,B,C 第N个任务带A去A的好感度会增加A[I] B,C同理
每个任务必须恰好带两个伙伴去完成 求一个方案使得所有任务完成后A,B,C三人的好感度相同,若存在多解输出好感度最大的
题解:
看N<=25不难想到搜索 然而3^n依然太大
于是考虑折半搜索
3^(n/2)大概是1000000左右 可以接受
现在的问题就变成了合并前后状态(a1,b1,c1)与(a2,b2,c2)使得$a1+a2=b1+b2=c1+c2$
整理一下可以得到$a2-b2=b1-a1,a2-c2=c1-a1$
所以只需要满足上面这两个要求就可以满足合并后三人好感度相同的要求
不难想到于是问题变成前半部分直接搜索得到(a1,b1,c1)这样的三元组 将它映射到三元组(a1-b1,a1-c1,a1)
后半部分直接搜索得到(a2,b2,c2)三元组后 查找前半部分存在的三元组(b2-a2,c2-a2,x)中x的最大值
于是我们用个map存一下三元组(a1-b1,a1-c1）这样的状态对应的最大的a1即可
//一开始我没有搜索而是用$3^n$这样表示的状态 然而这样需要乘以10的分解复杂度就TLE了QAQ
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
int n;
LL sum,ansx,ansy,ans=-1e18;
LL a[30],b[30],c[30];
LL dq,aa,bb,cc;
map<pair<LL,LL>,LL> mp;
map<pair<LL,LL>,LL> mp2;
struct Node
{
LL x,y;
friend bool operator > (Node a,Node b)
{
return a.x>b.x;
}
}now;
LL f[30];
int nn;
void dfs(int x,LL aa,LL bb,LL cc,LL i)
{
if (x==nn+1)
{
if (mp.count(make_pair(aa-bb,aa-cc))==0)
{
mp[make_pair(aa-bb,aa-cc)]=aa;
mp2[make_pair(aa-bb,aa-cc)]=i;
}
else
if (mp[make_pair(aa-bb,aa-cc)]<aa)
{
mp[make_pair(aa-bb,aa-cc)]=aa;
mp2[make_pair(aa-bb,aa-cc)]=i;
}
return;
}
dfs(x+1,aa+a[x],bb+b[x],cc,i*3);
dfs(x+1,aa,bb+b[x],cc+c[x],i*3+1);
dfs(x+1,aa+a[x],bb,cc+c[x],i*3+2);
}
void Dfs(int x,LL aa,LL bb,LL cc,LL i)
{
if (x==n+1)
{
if (mp.count(make_pair(bb-aa,cc-aa))==0) return;
dq=aa+mp[make_pair(bb-aa,cc-aa)];
if (dq>ans)
{
ans=dq;
ansx=mp2[make_pair(bb-aa,cc-aa)];
ansy=i;
}
return;
}
Dfs(x+1,aa+a[x],bb+b[x],cc,i*3);
Dfs(x+1,aa,bb+b[x],cc+c[x],i*3+1);
Dfs(x+1,aa+a[x],bb,cc+c[x],i*3+2);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%I64d%I64d%I64d",&a[i],&b[i],&c[i]);
nn=n/2;
//0:12 1:23 2:13
dfs(1,0,0,0,0);
Dfs(nn+1,0,0,0,0);
if (ans==-1e18) printf("Impossible\n");
else
{
dq=ansx;
for (int j=nn;j>=1;--j)
{
f[j]=dq%3;
dq/=3;
}
dq=ansy;
for (int j=n;j>=nn+1;--j)
{
f[j]=dq%3;
dq/=3;
}
for (int j=1;j<=n;++j)
{
if (f[j]==0) cout<<"LM"<<endl;
if (f[j]==1) cout<<"MW"<<endl;
if (f[j]==2) cout<<"LW"<<endl;
}
}
return 0;
}