题目看懂用了半个小时（英语不好+有道蹩脚翻译QWQ）
一（亿）眼看出是道比较容易的模拟
思路：对于每个公主喜欢的王子从小到大扫描，找到一对未标记的，两人都标记且夫妻对数sum++。如果sum=n，表示全部结婚，输出OPTIMAL，否则分别扫描公主和王子，扫到一个未标记的就输出编号
值得一提的是，这道题输入时间复杂度竟然有n^3，n<=1e5,于是cf上一开始是这样的
TLE代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define PII pair<int,int> #define fr(i,a,b) for(int i=a;i<=b;i++) #define fo(i,a,b) for(int i=a;i>=b;i--) //#pragma GCC optimize(2) int t,n,f1[100005],f2[100005]; int main(){ scanf("%d",&t); while(t--){ int sum=0; memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); scanf("%d",&n); fr(i,1,n){ int g; scanf("%d",&g); int flag=0; fr(j,1,g){ int x; scanf("%d",&x); if(f2[x]==0&&flag==0) { f2[x]=1; f1[i]=1; flag=1; sum++; } } } if(sum==n){ printf("OPTIMAL\n"); } else{ printf("IMPROVE\n"); fr(i,1,n) if(f1[i]==0) { printf("%d ",i); break; } fr(i,1,n) if(f2[i]==0) { printf("%d\n",i); break; } } } return 0; }
然后就各种降低常数复杂度，最后打了O2+快读就过了
AC代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define PII pair<int,int> #define fr(i,a,b) for(int i=a;i<=b;i++) #define fo(i,a,b) for(int i=a;i>=b;i--) #pragma GCC optimize(2) int t,n,f1[100005],f2[100005]; inline int read() { char ch = getchar(); int x = 0, f = 1; while(ch < ‘0‘ || ch > ‘9‘) { if(ch == ‘-‘) f = -1; ch = getchar(); } while(‘0‘ <= ch && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); } return x * f; } int main(){ t=read(); while(t--){ int sum=0; n=read(); fr(i,1,n) f1[i]=f2[i]=0;//初始化 fr(i,1,n){ int g=read(); int x[100005]; fr(j,1,g) x[j]=read(); fr(j,1,g){ if(f2[x[j]]==0) {//找到还没结婚的王子，标记掉 f2[x[j]]=1; f1[i]=1;//结婚 sum++;//对数++ break; } } } if(sum==n) puts("OPTIMAL"); else{ puts("IMPROVE"); fr(i,1,n) if(f1[i]==0) { printf("%d ",i); break; } fr(i,1,n) if(f2[i]==0) { printf("%d\n",i); break; } } } return 0; }
B题写了将近一个小时，我心态崩了ya
CF1327B Princesses and Princes
原文：https://www.cnblogs.com/shaozhihang/p/12558208.html