A. Surrender to My Will
直接判断当前是否不可翻盘。
点击查看代码
#include<cstdio>
using namespace std;
int main()
{
char str[10]; scanf("%s",str);
int y=0,n=0;
for(int i=0;i<5;i++)
{
if(str[i]=='Y') y++;
if(str[i]=='N') n++;
}
if(y>=4) printf("1\n");
else if(n>=2) printf("-1\n");
else printf("0\n");
return 0;
}
B. std::pair
让我想起了去年 CSP-S2023 T3 的没好回忆（手写结构体）。
把题目中给的类型递归建成一棵（二叉）树，叶节点表示 double 或 int，非叶节点表示 pair。
通过首字母判断当前是哪一种，如果是叶节点就设置完节点信息直接返回；否则先找递归找左叶节点（first），递归的同时返回子节点编号和该节点对应的字符串右端点，通过左叶节点的右端点找到字符串中右叶节点的起始位置，再递归处理寻找右子节点。
查询就更简单了，把字符串拆解成一连串 first 和 second，根据这个决定走左叶节点还是右叶节点。
注意存储的时候不要在节点内存整个节点对应的字符串，会爆空间。可以存类型编号或直接存类型名称之类的。
#include<cstdio>
#include<map>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;
int n,q;
map<string,int> raw;
struct JC_Pair{
string name;
int p1,p2;
}p[N*N];
int pidx=0;
string type,var;
pair<int,int> get_pair(int l) //返回 {索引，右端点}
{
int now=++pidx;
if(type[l]=='p') //pair<first,second>
{
pair<int,int> sonl=get_pair(l+5); //first
int sonl_idx=sonl.first,mid=sonl.second;
p[now].p1=sonl_idx;
pair<int,int> sonr=get_pair(mid+2); //second
int sonr_idx=sonr.first,end=sonr.second;
p[now].p2=sonr_idx;
p[now].name="pair";
return {now,end+1};
}
if(type[l]=='i') //int
{
p[now]={"int",0,0};
return {now,l+2};
}
if(type[l]=='d') //double
{
p[now]={"double",0,0};
return {now,l+5};
}
printf("ERROR!\n");
return {-1,-1};
}
void print_pair(int x)
{
printf("%s",p[x].name.c_str());
if(p[x].name=="pair")
{
putchar('<');
print_pair(p[x].p1);
putchar(',');
print_pair(p[x].p2);
putchar('>');
}
return;
}
string ts,tt;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
cin>>type>>var;
pair<int,int> tmp=get_pair(0);
raw[var]=tmp.first;
}
for(int i=1;i<=q;i++)
{
cin>>ts;
tt.clear();
int pos=0; bool is_name=true;
int now=0;
while(pos<=(int)ts.length())
{
if(pos==(int)ts.length() || ts[pos]=='.')
{
if(is_name)
{
now=raw[tt+';'];
is_name=false;
}
else
{
if(tt=="first") now=p[now].p1;
else if(tt=="second") now=p[now].p2;
else printf("ERROR!\n");
}
tt.clear();
}
else
{
tt+=ts[pos];
}
pos++;
}
print_pair(now);
putchar('\n');
}
return 0;
}
F. Collinear Exception
因为每行出现超过两个点就一定会在这一行三点共线，所以每行最多两个，一共最多 \(2n\) 个点。
那么我们就可以维护一张图，标明空位和被某条直线覆盖的位置。每次一个点若成功加入，则将它与其它所有已经加入的点组合连直线来标记图上被这条直线覆盖的点。
本人数学不好，只能算出来时间复杂度不高于 \(O(N^3)\)，但看这个样子应该是 \(O(N^2 \ln N)\) 之类的复杂度吧。
#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
using namespace std;
int read_u()
{
int x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
return x;
}
const int N=1005,M=N*N;
int n,x[M],y[M];
int avail_n,avail_x[M],avail_y[M];
bool unavail[N][N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
n=read_u();
for(int i=1;i<=n*n;i++)
{
x[i]=read_u(),y[i]=read_u();
if(unavail[x[i]][y[i]]) putchar('0');
else
{
putchar('1');
unavail[x[i]][y[i]]=true;
for(int j=1;j<=avail_n;j++)
{
int ax=avail_x[j],ay=avail_y[j];
int dx=x[i]-ax,dy=y[i]-ay; //绝对值不能再这里取！否则斜率一定非负！
int d=gcd(abs(dx),abs(dy)); dx/=d,dy/=d;
int tx=x[i],ty=y[i];
while(tx>=1&&tx<=n && ty>=1&&ty<=n)
{
unavail[tx][ty]=true;
tx+=dx,ty+=dy;
}
tx=x[i],ty=y[i];
while(tx>=1&&tx<=n && ty>=1&&ty<=n)
{
unavail[tx][ty]=true;
tx-=dx,ty-=dy;
}
}
avail_n++,avail_x[avail_n]=x[i],avail_y[avail_n]=y[i];
}
}
return 0;
}