GCJ2019 Round1C 题解
程序员文章站
2022-06-09 19:18:34
...
A.Robot Programming Strategy
就是看一下能不能干掉所有人,建个字典树,树上搜一下,如果再某一层有三种不同的情况那这棵子树就无解
#include<bits/stdc++.h>
using namespace std;
int hsh[27];
char rehsh[3];
struct node{
int c[3];
int su;
}tree[150000];
int cnt=0;
char str[550];
stack<int>ans;
void init(){
memset(tree,0,sizeof tree);
cnt=0;
hsh['R'-'A']=0;rehsh[0]='R';
hsh['P'-'A']=1;rehsh[1]='P';
hsh['S'-'A']=2;rehsh[2]='S';
}
void Insert(int rt,int p){
if(p==500)return;
int q=hsh[str[p]-'A'];
if(tree[rt].c[q]){
Insert(tree[rt].c[q],p+1);
}else{
tree[rt].c[q]=++cnt;
tree[rt].su++;
Insert(cnt,p+1);
}
}
int solve(int rt){
if(tree[rt].su==1){
for(int i=0;i<3;i++){
if(tree[rt].c[i]){
ans.push((i+1)%3);
}
}
return 1;
}
else if(tree[rt].su==3){
return 0;
}
else{
for(int i=0;i<3;i++){
int son=tree[rt].c[i];
if(!son){
int nxt=(i+2)%3;
int ns=tree[rt].c[nxt];
if(solve(ns)){
ans.push(nxt);
return 1;
}
}
}
return 0;
}
}
int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
int n;
init();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",str);
int len=strlen(str);
for(int i=len;i<500;i++){
str[i]=str[i-len];
}
str[500]=0;
Insert(0,0);//puts("1");
}
printf("Case #%d: ",cas);
if(!solve(0))puts("IMPOSSIBLE");
else {
while(!ans.empty()){
printf("%c",rehsh[ans.top()]);
ans.pop();
}
puts("");
}
}
return 0;
}
B.Power Arrangers
交互题,思路很简单
先扫第一位,找到不够的第一位的类,这类只有23个,以此类推
#include<bits/stdc++.h>
using namespace std;
vector<int>mv[5];
int ans[5];
int cnt=0;
int main(){
int t,f;
char str[3];
scanf("%d%d",&t,&f);
for(int cas=1;cas<=t;cas++){
for(int i=0;i<5;i++)mv[i].clear();
cnt=0;
for(int i=0;i<119;i++){
printf("%d\n",i*5+1);
fflush(stdout);
scanf("%s",str);
int p=str[0]-'A';
mv[p].push_back(i*5+1);
}
for(int i=0;i<5;i++){
if(mv[i].size()==23){
ans[cnt++]=i;
}
else mv[i].clear();
}
//printf("ans[cnt]=%d\n",ans[cnt]);
for(int i=0;i<23;i++){
printf("%d\n",mv[ans[cnt-1]][i]+1);
fflush(stdout);
scanf("%s",str);
int p=str[0]-'A';
mv[p].push_back(mv[ans[cnt-1]][i]+1);
}
for(int i=0;i<5;i++){
if(mv[i].size()==5){
ans[cnt++]=i;
}
else mv[i].clear();
}
//printf("ans[cnt]=%d\n",ans[cnt]);
for(int i=0;i<5;i++){
printf("%d\n",mv[ans[cnt-1]][i]+1);
fflush(stdout);
scanf("%s",str);
int p=str[0]-'A';
mv[p].push_back(mv[ans[cnt-1]][i]+1);
}
for(int i=0;i<5;i++){
if(mv[i].size()==1){
ans[cnt++]=i;
}
else mv[i].clear();
}
/// printf("ans[cnt]=%d\n",ans[cnt]);
for(int i=0;i<1;i++){
printf("%d\n",mv[ans[cnt-1]][i]+1);
fflush(stdout);
scanf("%s",str);
int p=str[0]-'A';
mv[p].push_back(mv[ans[cnt-1]][i]+1);
}mv[ans[cnt-1]].clear();
for(int i=0;i<5;i++){
if(mv[i].size()==1){
ans[cnt++]=i;
}
else mv[i].clear();
}
int sum=10;
for(int i=0;i<4;i++){
sum-=ans[i];
//printf("%d\n",ans[i]);
}
ans[4]=sum;
swap(ans[4],ans[3]);
for(int i=0;i<5;i++){
printf("%c",ans[i]+'A');
}puts("");
fflush(stdout);
scanf("%s",str);
if(str[0]=='Y')continue;
else break;
}
return 0;
}
C不会,待补
上一篇: 5G新空口资源