一句话题意:
A：给出两个长为\(n\)，\(m\)的的数组，每个数在\(1\)到\(9\)之间，求出一个最小的数使得至少有一位出现在一个数组中，且至少有一位出现在另一个数组中。\(n,m\leq9\) B：给出一个长度为\(n\)的数组\(a\)，将它分成\(k\)段，最大化每一段最小值的最大值。\(1\leq{k}\leq{n}\leq10^5,-10^9\leq{a_i}\leq10^9\) C：\(q\)个询问将自然数\(n\)最多能分成多少个合数的和。\(q\leq{10^5},1\leq{n}\leq{10^9}\) D：交互题。有一个排列\(p\)但你不知道，你只知道它的长度\(n\)，然后还有一个排列\(b\)满足\(\forall{i}\in[1,n],p_{b_i}=i\)，你每次可以询问\(p_i\ xor\ b_j\)的值，不能询问超过\(2\times{n}\)次，然后注意到即使询问\(n^2\)次这个数组也不一定只有唯一解，因此你需要输出这个数组的合法解的个数和任意一组解。\(n\leq5000\)，排列从\(0\)开始标号。 E：给出平面上的\(n\)个点，每个点可以选择什么事儿都不干，画一条垂线或画一条水平线，如果出现重叠算作是一根线，问可能出现的图形的方案数对\(10^9+7\)取模。\(n\leq{10^5},-10^9\leq{x_i,y_i}\leq10^9\)题解：
A：直接贪心，答案的位数肯定小于等于\(2\)，然后注意特判一下答案是一位数的情况。#include#include #include #include #include using namespace std;int n,m,mna,mnb;int a[100],b[100];bool visa[100],visb[100];inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void print(int x){ if (x<0){putchar('-'); x=-x;} if (x>=10) print(x/10); putchar(x%10+'0');}int main(){ n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(),visa[a[i]]=1; for (int i=1;i<=m;i++) b[i]=read(),visb[b[i]]=1; for (int i=1;i<=9;i++) if (visa[i]&&visb[i]){printf("%d\n",i); return 0;} for (int i=1;i<=9;i++) if (visa[i]){mna=i; break;} for (int i=1;i<=9;i++) if (visb[i]){mnb=i; break;} printf("%d%d\n",min(mna,mnb),max(mna,mnb)); return 0;}
B：当\(k=1\)时直接输出最小值，当\(k\geq3\)时直接输出最大值，否则枚举从哪分开记一个前缀后缀\(min\)即可，当然也可以直接输出\(max(a_1,a_n)\)
#include#include #include #include #include using namespace std;#define maxn 100005const int inf=2e9;int n,k,mx=-inf,mn=inf,ans=-inf;int a[maxn],pre[maxn],suf[maxn];inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void print(int x){ if (x<0){putchar('-'); x=-x;} if (x>=10) print(x/10); putchar(x%10+'0');}int main(){ n=read(),k=read(); for (int i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]),mn=min(mn,a[i]); if (k==1){printf("%d\n",mn); return 0;} if (k>=3){printf("%d\n",mx); return 0;} pre[0]=inf; for (int i=1;i<=n;i++) pre[i]=min(pre[i-1],a[i]); suf[n+1]=inf; for (int i=n;i;i--) suf[i]=min(suf[i+1],a[i]); for (int i=1;i
C：首先把不合法的判掉，然后肯定是分成若干个\(4\)更优，然后各种特判细节详见代码。
#include#include #include #include #include using namespace std;int n,m;inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void print(int x){ if (x<0){putchar('-'); x=-x;} if (x>=10) print(x/10); putchar(x%10+'0');}int main(){ for (int T=read();T;T--){ n=read(); if (n<=3){puts("-1"); continue;} if (n%4==0) printf("%d\n",n/4); else if (n%4==1){ if (n==5) puts("-1"); else printf("%d\n",n/4-1); } else if (n%4==2) printf("%d\n",n/4); else{ if (n==7||n==11) puts("-1"); else printf("%d\n",n/4-1); } } return 0;}
D：别被交互题给吓懵逼了，反正对于我这种从来没做过交互题的菜鸡就直接跳了，结果搞清楚套路才发现这就是一道思博题。
询问就直接询问\(p[0]\)对\(b\)数组每一个元素的异或值以及\(b[0]\)对\(p\)数组每一个元素的异或值，然后直接枚举\(p[0]\)就能算出\(b\)数组进而算出\(p\)数组，然后判一判是否合法就完了。。。反正可以\(n^2\)以及这是cf的机子瞎捷豹暴力就好了。。。。#include#include #include #include #include using namespace std;#define maxn 5005int n,m,cnt,flag=1;int a[maxn],b[maxn],c[maxn],d[maxn],ans[maxn];inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void print(int x){ if (x<0){putchar('-'); x=-x;} if (x>=10) print(x/10); putchar(x%10+'0');}int main(){ n=read(); for (int i=0;i
E：首先离散化还是必须的，然后我们把一个点能作的两条直线看成是一个图中的一个点，然后把它们俩之间连一条边，显然这个图会有许许多多的连通块，然后连通块之间互不影响，考虑对每一个连通块计数，最后乘起来就好了。
首先可以把题意转化成这么样的一个东西：连通块的每条边都是无向边，现在每条边可以定方向，要么是\(u\to{v}\)，要么是\(v\to{u}\)，要么不管它，然后问最后入度不为\(0\)的点的集合的方案数。 首先考虑如果连通块是树的情况怎么求首先设连通块的大小为\(n\)，树的话首先不可能每个点都被选，因为一共才\(n-1\)条边，然后除此之外任意的情况都存在，证明的话就是考虑任意一个大小为\(n-1\)的集合都合法，因为我们可以把剩下的那个点作为根，然后每一条边都定向为父亲指向儿子即可，然后这些集合的任意一个子集也是合法的，因为边我可以不定向，因而得证。也就是说树的情况答案就是\(2^n-1\) 然后如果一旦存在环，那么答案就是\(2^n\)，这个也很简单证，一定可以构造出一种方案使得每个点都被选上，假设这个图比树多了一条边\(<u,v>\)，我们只需要忽视这条边然后以\(u\)为根按照树的情况定向，然后这条边定向为\(v\to{u}\)即可。也就是说不是树那么答案就是\(2^n\) 然后用并查集维护即可。#include#include #include #include #include using namespace std;#define maxn 100005const int mod=1e9+7;int n,m,cnt_x,cnt_y,ans=1;int vx[maxn],vy[maxn];struct point{int x,y;}p[maxn];inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void print(int x){ if (x<0){putchar('-'); x=-x;} if (x>=10) print(x/10); putchar(x%10+'0');}struct union_find_set{ int fa[maxn*2],size[maxn*2]; bool cir[maxn*2]; void initialize(){for (int i=1;i<=2*n;i++) fa[i]=i;} int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void merge(int x,int y){ x=find(x),y=find(y); if (x==y) cir[x]=1; else fa[x]=y,cir[y]|=cir[x]; }}u;int power(int a,int k){ int ret=1; for (;k;k>>=1,a=1ll*a*a%mod) if (k&1) ret=1ll*ret*a%mod; return ret;}int main(){ n=read(); u.initialize(); for (int i=1;i<=n;i++){ p[i].x=read(),p[i].y=read(); vx[++cnt_x]=p[i].x,vy[++cnt_y]=p[i].y; } sort(vx+1,vx+cnt_x+1); int tmp_x=unique(vx+1,vx+cnt_x+1)-vx-1; for (int i=1;i<=n;i++) p[i].x=lower_bound(vx+1,vx+tmp_x+1,p[i].x)-vx; sort(vy+1,vy+cnt_y+1); int tmp_y=unique(vy+1,vy+cnt_y+1)-vy-1; for (int i=1;i<=n;i++) p[i].y=lower_bound(vy+1,vy+tmp_y+1,p[i].y)-vy; for (int i=1;i<=n;i++) u.merge(p[i].x,p[i].y+n); for (int i=1;i<=tmp_x;i++) ++u.size[u.find(i)]; for (int i=1;i<=tmp_y;i++) ++u.size[u.find(i+n)]; for (int i=1;i<=(n<<1);i++) if (u.size[i]){ ans=1ll*ans*(power(2,u.size[i])-(!u.cir[i]))%mod; } printf("%d\n",(ans+mod)%mod); return 0;}