下午到了机房之后又困又饿，还要被强行摁着看英文题，简直差评
第一题是NOIP模拟赛的原题，随便模拟就好啦
本人模拟功力太渣不小心打错了个变量，居然调了40多分钟QAQ
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std; const int maxn=100010;
char s[10][maxn];
int Num[maxn];
int a,b,n,k,now; int check(int L,int R){
int cnt=0;
for(int i=1;i<=7;++i)for(int j=L;j<=R;++j)if(s[i][j]=='x')cnt++;
if(cnt==7)return 1;
if(cnt==9)return -1;
if(cnt==11)return 7;
if(cnt==23)return 8;
if(cnt==20)return 0;
if(cnt==14)return 4;
if(cnt==19){
if(s[5][L]=='x')return 2;
if(s[2][L]=='x')return 5;
return 3;
}
if(cnt==21){
if(s[5][L]=='x')return 6;
return 9;
}return 0;
}
void Get_print(int L,int R,int k){
if(k==0){
for(int i=L;i<=R;++i)s[1][i]='x',s[7][i]='x';
for(int i=2;i<=6;++i){
for(int j=L;j<=R;++j){
if(j==L||j==R)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==1){
for(int i=1;i<=7;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==2){
for(int i=L;i<=R;++i)s[1][i]=s[4][i]=s[7][i]='x';
for(int i=2;i<=3;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}
for(int i=5;i<=6;++i){
for(int j=L;j<=R;++j){
if(j==L)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==3){
for(int i=L;i<=R;++i)s[1][i]=s[4][i]=s[7][i]='x';
for(int i=2;i<=3;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}
for(int i=5;i<=6;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==4){
for(int i=1;i<=3;++i){
for(int j=L;j<=R;++j){
if(j==L||j==R)s[i][j]='x';
else s[i][j]='.';
}
}
for(int i=L;i<=R;++i)s[4][i]='x';
for(int i=5;i<=7;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==5){
for(int i=L;i<=R;++i)s[1][i]=s[4][i]=s[7][i]='x';
for(int i=2;i<=3;++i){
for(int j=L;j<=R;++j){
if(j==L)s[i][j]='x';
else s[i][j]='.';
}
}
for(int i=5;i<=6;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==6){
for(int i=L;i<=R;++i)s[1][i]=s[4][i]=s[7][i]='x';
for(int i=2;i<=3;++i){
for(int j=L;j<=R;++j){
if(j==L)s[i][j]='x';
else s[i][j]='.';
}
}
for(int i=5;i<=6;++i){
for(int j=L;j<=R;++j){
if(j==R||j==L)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==7){
for(int i=L;i<=R;++i)s[1][i]='x';
for(int i=2;i<=7;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==8){
for(int i=L;i<=R;++i)s[1][i]=s[4][i]=s[7][i]='x';
for(int i=2;i<=3;++i){
for(int j=L;j<=R;++j){
if(j==L||j==R)s[i][j]='x';
else s[i][j]='.';
}
}
for(int i=5;i<=6;++i){
for(int j=L;j<=R;++j){
if(j==R||j==L)s[i][j]='x';
else s[i][j]='.';
}
}return;
}
if(k==9){
for(int i=L;i<=R;++i)s[1][i]=s[4][i]=s[7][i]='x';
for(int i=2;i<=3;++i){
for(int j=L;j<=R;++j){
if(j==L||j==R)s[i][j]='x';
else s[i][j]='.';
}
}
for(int i=5;i<=6;++i){
for(int j=L;j<=R;++j){
if(j==R)s[i][j]='x';
else s[i][j]='.';
}
}return;
}return;
}
void print(int n){
int len=0,u=n;
if(!n)Num[++len]=0;
else{while(n)Num[++len]=n%10,n/=10;}
for(int i=len;i>=1;--i){
int L=(len-i)*6+1,R=(len-i+1)*6-1;
Get_print(L,R,Num[i]);
for(int j=1;j<=7;++j)s[j][R+1]='.';
}
len=len*6-1;
for(int i=1;i<=7;++i){
for(int j=1;j<=len;++j){
putchar(s[i][j]);
}printf("\n");
}
return;
} int main(){
for(int i=1;i<=7;++i)scanf("%s",s[i]+1);
a=b=0;n=strlen(s[1]+1);k=(n+1)/6;
now=0;
for(int i=1;i<=k;++i){
int L=(i-1)*6+1,R=i*6-1;
int c=check(L,R);
if(c==-1)a=now,now=0;
else now=now*10+c;
}b=now;
b=a+b;
print(b);
return 0;
}
第二题考场上只想出了对a和b的处理方式，没有想出c的处理方式
貌似c要用NTT，还是模任意质数的NTT，决定去学习一发(坑ing)
第三题考场上并没有做出来，首先题目奇怪的输入保证了每个点的出度均为1，且图中只存在偶环
我们不妨考虑什么样的点一定在集合内，显然如果他入度为0，那么一定在集合内
那么这个点所能到达的点就一定不能选了，把这两个点删掉之后，原图会又出现一些入度为0的点
这样重复若干次之后原图剩下的就只有偶环了，对于偶环我们任取二分图的一侧染色即可
细节略多，自己画画图推一推也能把细节都推出来
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std; const int maxn=200010;
int n,u;
int to[maxn];
int deg[maxn];
int vis[maxn];
int ans[maxn],tot=0;
queue<int>Q;
void toposort(){
for(int i=1;i<=n;++i)if(deg[i]==0)Q.push(i),vis[i]=1;
while(!Q.empty()){
int u=Q.front();Q.pop();
int now=to[u];
if(vis[now]!=-1)continue;
vis[now]=0;
int v=to[now];deg[v]--;
if(deg[v]==0&&vis[v]==-1)vis[v]=1,Q.push(v);
}return;
}
int main(){
scanf("%d",&n);n<<=1;
for(int i=1;i<=n;++i){
scanf("%d",&u);
to[i]=u;deg[u]++;
}
memset(vis,-1,sizeof(vis));
toposort();
for(int i=1;i<=n;++i){
if(vis[i]==-1){
if(i<=(n>>1))ans[++tot]=i;
}else{
if(vis[i])ans[++tot]=i;
}
}
for(int i=1;i<=tot;++i){
printf("%d",ans[i]);
if(i==tot)printf("\n");
else printf(" ");
}return 0;
}
第四题是BC的原题的弱化版
一开始看错题以为求字典序最小的解结果各种挂QAQ
如果这些数有奇数个，sum=中位数*数的数量
如果有偶数个，sum=(首项+尾项)*数的数量/2
都是乘法，枚举因子搞一搞就好啦
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std; const int oo=0x7fffffff;
int T,n;
int L,len; void check(int i){
int k=n/i;
if(k&1){
int now=(i-k/2);
if(now>0){
if(k<len&&k!=1)len=k,L=now;
}
}
if(i&1){
int now=((i>>1)-k+1);
k<<=1;
if(now>0){
if(k<len&&k!=1)len=k,L=now;
}
}return;
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
if(n==1){printf("IMPOSSIBLE\n");continue;}
if(n&1){
printf("%d = ",n);
printf("%d + %d\n",n>>1,(n>>1)+1);
continue;
}
int m=(int)(sqrt(n+0.5))+1;
L=oo;len=oo;
for(int i=1;i<=m;++i){
if(n%i==0){
check(i);
if(i*i!=n)check(n/i);
}
}
if(L==oo)printf("IMPOSSIBLE\n");
else{
printf("%d = ",n);
for(int i=0;i<len;++i){
printf("%d ",L+i);
if(i!=len-1)printf("+ ");
}printf("\n");
}
}return 0;
}
第五题首先如果一个*被影响，显然比例是第一个*的R和这个*的R的比
关键是判断逆时针和顺时针，我们发现由于数据造的很好，不存在三个*互相相交的情况
那么显然第一个是逆时针，第一个影响到的是顺时针，再影响到的是逆时针。。。BFS一遍即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std; const int maxn=1010;
int T,n;
int vis[maxn];
struct C{
double x,y,r;
}c[maxn];
int h[maxn],cnt=0;
struct edge{
int to,next;
}G[2000010];
queue<int>Q;
int GCD(int a,int b){return b==0?a:GCD(b,a%b);}
void add(int x,int y){
cnt++;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;
}
double dis(const C &A,const C &B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
void BFS(){
Q.push(1);vis[1]=0;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v]!=-1)continue;
vis[v]=(vis[u]^1);
Q.push(v);
}
}return;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(vis,-1,sizeof(vis));
for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&c[i].x,&c[i].y,&c[i].r);
memset(h,0,sizeof(h));cnt=0;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(dis(c[i],c[j])<=c[i].r+c[j].r){
add(i,j);add(j,i);
}
}
}BFS();
for(int i=1;i<=n;++i){
if(vis[i]==-1)printf("not moving\n");
else{
int A=(int)(c[i].r+0.1),B=(int)(c[1].r+0.1);
int d=GCD(A,B);
A/=d;B/=d;
if(A==1)printf("%d ",B);
else printf("%d/%d ",B,A);
if(vis[i]==1)printf("counterclockwise\n");
else printf("clockwise\n");
}
}
}return 0;
}
第六题我还能说些什么呢，数据范围貌似暴力都可以过去啦
正常点的写法就是矩形面积并的裸题
由于本人忘记了线段树上的标记怎么维护了思考了很久，差点就要写分块了
(不过分块还是很好写的，捂脸。。）
写分块的过程中就领悟了标记怎么维护QAQ，然后写成线段树跑的飞快
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define eps 1e-4
using namespace std; const int maxn=400010;
int n,kase,cnt,m;
double a,b,cc,d;
double pos[maxn];
struct Seg{
double l,r,h;
int type;
}c[maxn];
struct Seg_Tree{
int cnt;
double len;
}t[maxn<<2];
bool cmp(const Seg &A,const Seg &B){
return A.h<B.h;
}
void build(int o,int L,int R){
t[o].cnt=t[o].len=0;
if(L==R)return;
int mid=(L+R)>>1;
build(o<<1,L,mid);
build(o<<1,mid+1,R);
}
int Get_pos(double v,int L,int R){
while(L<=R){
int mid=(L+R)>>1;
if(fabs(pos[mid]-v)<eps)return mid;
else if(v<pos[mid])R=mid-1;
else L=mid+1;
}return 0;
}
void Get_len(int o,int L,int R){
if(t[o].cnt)t[o].len=pos[R+1]-pos[L];
else if(L==R)t[o].len=0;
else t[o].len=t[o<<1].len+t[o<<1|1].len;
}
void UPD(int o,int L,int R,int x,int y,int v){
if(L>=x&&R<=y){
t[o].cnt+=v;
Get_len(o,L,R);
return;
}
int mid=(L+R)>>1;
if(y<=mid)UPD(o<<1,L,mid,x,y,v);
else if(x>mid)UPD(o<<1|1,mid+1,R,x,y,v);
else {UPD(o<<1,L,mid,x,y,v);UPD(o<<1|1,mid+1,R,x,y,v);}
Get_len(o,L,R);
} int main(){
while(scanf("%d",&n)==1){
if(!n)break;
kase++;cnt=0;
for(int i=0;i<n;i++){
scanf("%lf%lf%lf%lf",&a,&b,&cc,&d);
cnt++;
c[cnt].l=a;c[cnt].r=cc;c[cnt].h=b;c[cnt].type=1;
pos[cnt]=a;
cnt++;
c[cnt].l=a;c[cnt].r=cc;c[cnt].h=d;c[cnt].type=-1;
pos[cnt]=cc;
}
sort(c+1,c+cnt+1,cmp);
sort(pos+1,pos+cnt+1);
m=0;pos[0]=-1;
for(int i=1;i<=cnt;++i){
if(pos[i]!=pos[i-1])pos[++m]=pos[i];
}
build(1,1,m);
double ans=0;
for(int i=1;i<=cnt;++i){
int L=Get_pos(c[i].l,1,m);
int R=Get_pos(c[i].r,1,m)-1;
if(L<=R)UPD(1,1,m,L,R,c[i].type);
ans+=(c[i+1].h-c[i].h)*t[1].len;
}
printf("Test case #%d\n",kase);
printf("Total explored area: %.2lf\n\n",ans);
}return 0;
}
考试中较好的地方：这场考试并没有什么较好的地方
考试中较差的地方：
1、模拟居然需要调试！
2、第三题应该多推导而不是直接套二分图的模型的
3、第五题应该早点看，最后几分钟才写完，真是危险
4、模板还是不熟练，矩形面积并居然差点忘掉