传送门
首先是贪心的思路
从后向前选，能多选就多选，
理由：数字越少肯定越优，同时间隔尽量向前推，字典序尽量小
对于K==1，枚举1~512直接判断
对于K==2，需要用镜像并查集，来刻画“敌对关系”，如果a和b产生矛盾，就把a和b的镜像（b'）连接 ，b和a'连接，然后判断自己是不是和自己的镜像连接了
打上时间戳避免清零卡常
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #include<vector> 6 #define MAXN 131100 7 using namespace std; 8 int n,K; 9 namespace solve1 10 { 11 int read(){ 12 int x=0;char ch=getchar(); 13 while(ch<'0'||ch>'9'){ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();} 15 return x; 16 } 17 int n,K,cnt; 18 int a[MAXN]; 19 int b[MAXN<<1]; 20 int p[512]; 21 vector<int> v; 22 int check(int x){ 23 for(int i=512;i>=0;i--){ 24 if(p[i]-x<=0){ 25 return 1; 26 } 27 if(b[p[i]-x]&&b[p[i]-x]==cnt){ 28 return 0; 29 } 30 } 31 return 1; 32 } 33 void solve(){ 34 n=::n,K=::K; 35 cnt=1; 36 for(int i=1;i<=512;i++){ 37 p[i]=i*i; 38 } 39 for(int i=1;i<=n;i++){ 40 a[i]=read(); 41 } 42 for(int i=n;i>=1;i--){ 43 if(check(a[i])){ 44 b[a[i]]=cnt; 45 } 46 else{ 47 cnt++; 48 b[a[i]]=cnt; 49 v.push_back(i); 50 } 51 } 52 printf("%d ",cnt); 53 for(int i=v.size()-1;i>=0;i--){ 54 printf("%d ",v[i]); 55 } 56 } 57 } 58 namespace solve2 59 { 60 int read(){ 61 int x=0;char ch=getchar(); 62 while(ch<'0'||ch>'9'){ch=getchar();} 63 while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();} 64 return x; 65 } 66 int f[MAXN<<1]; 67 vector<int> v[MAXN<<1]; 68 int vis[MAXN<<1]; 69 int p[512]; 70 int a[MAXN]; 71 int n,K; 72 int cnt; 73 vector<int> ans; 74 int find(int x){ 75 return (f[x]==x?x:f[x]=find(f[x])); 76 } 77 void lik(int x,int y){ 78 x=find(x),y=find(y); 79 if(x!=y){ 80 f[x]=y; 81 } 82 } 83 bool same(int x,int y){ 84 return (find(x)==find(y)); 85 } 86 int check(int x){ 87 for(int i=512;i>=1;i--){ 88 if(p[i]-a[x]<=0){ 89 return 1; 90 } 91 else if(vis[p[i]-a[x]]&&vis[p[i]-a[x]]==cnt){ 92 for(int j=0;j<v[p[i]-a[x]].size();j++){ 93 int t=v[p[i]-a[x]][j]; 94 if(same(x,t)){ 95 return 0; 96 } 97 lik(x,t+n); 98 lik(x+n,t); 99 } 100 } 101 } 102 return 1; 103 } 104 void solve(){ 105 n=::n,K=::K; 106 cnt=1; 107 for(int i=1;i<=512;i++){ 108 p[i]=i*i; 109 } 110 for(int i=1;i<=(n<<1);i++){ 111 f[i]=i; 112 } 113 for(int i=1;i<=n;i++){ 114 a[i]=read(); 115 } 116 for(int i=n;i>=1;i--){ 117 if(check(i)){ 118 if(vis[a[i]]!=cnt){ 119 vis[a[i]]=cnt; 120 v[a[i]].clear(); 121 } 122 v[a[i]].push_back(i); 123 } 124 else{ 125 cnt++; 126 vis[a[i]]=cnt; 127 v[a[i]].clear(); 128 v[a[i]].push_back(i); 129 ans.push_back(i); 130 } 131 } 132 printf("%d ",cnt); 133 for(int i=ans.size()-1;i>=0;i--){ 134 printf("%d ",ans[i]); 135 } 136 } 137 } 138 int main() 139 { 140 // freopen("data.in","r",stdin); 141 // freopen("a.out","w",stdout); 142 scanf("%d%d",&n,&K); 143 if(1==K){ 144 solve1::solve(); 145 } 146 else{ 147 solve2::solve(); 148 } 149 return 0; 150 }