题目链接
https://codeforces.com/gym/104059
A. Alternative Architecture
思路
简单题，但要注意细节。
给的方格很干扰思考，事实上注意到顶点指的是四个角上的圆圈，我们将长宽都减去\(1\)，问题就转化成了标准的格点矩形问题。
然后我们可以枚举左边的小三角形的直角边长\((x,y)\)，确定矩形的方向。简单利用一下相似三角形的性质就判定右上角的点是否在格点上。
注意这样枚举出来的方向是\((0,90)\)，根据\(a,b\)是否相等分类讨论才是最终答案。
时间复杂度\(\Theta(a)\)
代码
点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
int main(){
int ans=1;
ll a,b;
scanf("%lld%lld",&a,&b);
a--,b--;
if(a>b) swap(a,b);
for(int x=1;x<a;++x){
ll t=(a+x)*(a-x);
ll y=(ll)floor(sqrt(t));
if(y*y==t||(y+1)*(y+1)==t){
if(!(x*b%a)&&!(y*b%a)){
ans++;
}
}
}
if(a!=b) ans*=2;
printf("%d",ans);
return 0;
}
B. Breeding Bugs
思路
中档题，需要一些观察和灵感。
首先，看见\(n\leq 750\)，基本可以肯定不是数论推式子，那么就可能需要一些相对暴力的办法。
我们把相加为质数的两个数间连一条边，表示不能同时取，于是就变成了一个图的最大独立集问题。
但是一般图的最大独立集是非\(P\)类问题，但是作为特殊情况，二分图的最大独立集是非常简单的：最大独立集=总点数-最大匹配数
然后我们考虑这个图是不是二分图。
假设图上存在奇环，设环为\(k\)元环，那么：
\[a_1+a_2=p_1 \]\[a_2+a_3=p_2 \]\[...... \]\[a_k+a_1=p_k \]全部相加得\(2\sum_{i=1}^k a_i=\sum_{i=1}^k p_k\)。
注意到右边的\(p\)全部都是质数，而奇数个质数相加为奇数（？），推出矛盾，图上不存在二元环，所以图是二分图。
诶，不对，你这推理有问题啊，如果右边的\(p\)当中有\(2\)呢？那不是寄了？
但是我们注意到，\(1+1=2\)，所以我们在选数的过程中，最多选一个\(1\)，所以我们的\(p\)当中是不会出现\(2\)的。
于是，过滤掉多余的\(1\)，建图跑匈牙利就完事了。
时间复杂度\(\Theta(n^3)\)
有傻逼匈牙利写挂了，我不说是谁
代码
点击查看代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 760
#define lim 20000000
#define max_p 1400000
using namespace std;
int is_p[lim+1],p[max_p],cnt=0;
int a[maxn],tot=0;
int fst[maxn],nxt[maxn*maxn*2],to[maxn*maxn*2],e=0;
void sieve(){
int i,j;
memset(is_p,1,sizeof(is_p));
is_p[1]=0;
for(i=2;i<=lim;++i){
if(is_p[i]) p[++cnt]=i;
for(j=1;j<=cnt&&p[j]<=lim/i;++j){
is_p[i*p[j]]=0;
if(!(i%p[j])) break;
}
}
}
void add(int x,int y){
to[++e]=y;
nxt[e]=fst[x];
fst[x]=e;
}
int used[maxn],c[maxn],vis[maxn],match[maxn];
void paint(int x,int color){
c[x]=color;vis[x]=1;
for(int i=fst[x];i;i=nxt[i]){
if(vis[to[i]]) continue;
paint(to[i],color^1);
}
return;
}
int dfs(int x){
for(int i=fst[x];i;i=nxt[i]){
if(used[to[i]]) continue;
used[to[i]]=1;
if(!match[to[i]]||dfs(match[to[i]])){
match[to[i]]=x;
return 1;
}
}
return 0;
}
int main(){
int i,j,n,x,flag=1;
int ans=0;
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d",&n);
sieve();
for(i=1;i<=n;++i){
scanf("%d",&x);
if(x>1) a[++tot]=x;
else if(flag){
flag=0;
a[++tot]=x;
}
}
n=tot;
for(i=1;i<=n;++i){
for(j=i+1;j<=n;++j){
if(is_p[a[i]+a[j]]){
add(i,j),add(j,i);
}
}
}
for(i=1;i<=n;++i){
if(!vis[i]) paint(i,0);
}
for(i=1;i<=n;++i){
if(c[i]) continue;
for(j=1;j<=n;++j) used[j]=0;
ans+=dfs(i);
}
printf("%d\n",n-ans);
return 0;
}
C. Chaotic Construction
思路
简单题。
是个环，那么从\(a\)到\(b\)有\(a->b\)和\(a->1->n->b\)两条路可走。
我们只需要实时维护数组的区间和就可以了，如果路径上点全部被覆盖(值为1)就可达，否则不可达。
单点加，区间求和，我用的是树状数组。
时间复杂度\(\Theta(nlogn)\)。
代码
点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 200010
using namespace std;
int lowbit(int x){
return x&(-x);
}
int c[maxn],n,m;
void modify(int x,int d){
while(x<=n){
c[x]+=d;
x+=lowbit(x);
}
}
int query(int x){
int ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int main(){
int i,j,x,y;
char op[2];
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i) modify(i,1);
for(i=1;i<=m;++i){
scanf("%s",op);
if(op[0]=='?'){
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
int flag=0;
int sum=query(n)+query(x)-query(y-1);
flag|=(sum==n-y+1+x);
sum=query(y)-query(x-1);
flag|=(sum==y-x+1);
if(flag) printf("possible\n");
else printf("impossible\n");
}
else if(op[0]=='+'){
scanf("%d",&x);
modify(x,1);
}
else{
scanf("%d",&x);
modify(x,-1);
}
}
return 0;
}
D. Diabolic Doofenshmirtz
思路
简单题，但是容易写错。
第一次看错题了，以为是个简单二分，写上去寄了。
然后再审一遍题，发现要求询问的\(t\)严格递增。
这就比较麻烦了，但是观察一下数据范围，我们相信二分的思路是没错的，与数据吻合得非常好。
然后我们考虑怎么在\(t\)递增的情况下达成二分的效果。
手搓几组样例可以发现，交互时返回的\(d\)值，除了根据\(t\)和\(d\)的大小关系来判断是否兜了圈之外，我们还同时找到了圈长的倍数。
于是如果我们当前准备询问的\(t\)比上次小，我们可以不停加上这个倍数直到比上次大。
然后这题就做完了。
时间复杂度\(log(10^{12})\)。
代码
点击查看代码
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
int main(){
ll t,l=1,r=1ll<<40,d,ans,lap=-1;
t=l+r>>1;
while(l<=r){
printf("? %lld\n",t);
fflush(stdout);
scanf("%lld",&d);
ll mid=l+r>>1,dt;
if(d==mid) l=mid+1,dt=l+r>>1;
else{
r=mid-1;
if(!d) ans=mid;
if(t-d<lap||lap<0) lap=t-d;
dt=(l+r>>1);
}
if(dt<=t) dt+=((t-dt)/lap+1)*lap;
t=dt;
// printf("%lld %lld %lld\n",l,r,lap);
}
printf("! %lld",ans);
fflush(stdout);
return 0;
}
摸鱼了喵，剩下的题解明天写。。。
标签：Contest,int,sum,flag,maxn,补题,2022,include,define From： https://www.cnblogs.com/landmine-sweeper/p/17196756.html