请发代码
by TheUltimateLaw @ 2017-11-09 20:00:58
暴力
```cpp
#include<bits/stdc++.h>
#define pb push_back
#define forup(i,a,b) for(int i=(a);i<=(b);i++)
#define fordown(i,a,b) for(int i=(a);i>=(b);i--)
#define maxn 1000005
#define N 131073
#define INF 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline void read(T& num){ num = 0; bool f = true;char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();} while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();} num = f ? num: -num; }
int out[100];
template<class T> inline
void write(T x,char ch){ if (x==0) {putchar('0'); putchar(ch); return;} if (x<0) {putchar('-'); x=-x;} int num=0; while (x){ out[num++]=(x%10); x=x/10;} fordown(i,num-1,0) putchar(out[i]+'0'); putchar(ch); }
/*========================================================*/
int n,K;
int a[maxn];
int dp[maxn];
bool vis[maxn];
int cnt;
int ans[maxn];
bool check(int x)
{ bool flag=1;
for (int k = 1; k * k - a[x] < N; k++)
{ if (k * k - a[x] <= 0) continue;
if (vis[k * k - a[x]]) {flag = 0;break;}
}
return flag;
}
void cheat1()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check(l)) {vis[a[l]]=1;l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
for ( ; r > l; r--) vis[a[r]] = 0;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
vector<int> g[maxn];
bool sqr[maxn];
int col[maxn];
bool dfs(int x,int f)
{ col[x]=f;
bool flag=1;
for(int i=0;i<g[x].size();i++)
{int u=g[x][i];
if(col[x]==col[u]) {flag=0;break;}
if(col[u]==-1) flag=flag&dfs(u,f^1);
}
return flag;
}
bool check2(int l,int r)
{//cout<<"case"<<endl;
//cout<<l<<' '<<r<<endl;
bool flag=1;
forup(i,l,r)
forup(j,i+1,r)
{//cout<<i<<' '<<j<<endl;
if(sqr[a[i]+a[j]]) g[i].pb(j),g[j].pb(i);
}
forup(i,l,r) col[i]=-1;
forup(i,l,r) if(col[i]==-1) {if(dfs(i,0)==0) {flag=0;break;}}
forup(i,l,r) g[i].clear();
return flag;
}
void cheat2()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check2(l,r)) {l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
r=l;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
int main()
{freopen("division2.in","r",stdin);
//freopen("1.out","w",stdout);
forup(i,1,1000) sqr[i*i]=1;
cin>>n>>K;
forup(i,1,n) read(a[i]);
if(K==1)
{ cheat1();}
if(K==2)
{ cheat2();}
return 0;
}
```
by zhouyihe @ 2017-11-09 20:03:59
二分
```cpp
#include<bits/stdc++.h>
#define pb push_back
#define forup(i,a,b) for(int i=(a);i<=(b);i++)
#define fordown(i,a,b) for(int i=(a);i>=(b);i--)
#define maxn 1000005
#define N 131073
#define INF 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline void read(T& num){ num = 0; bool f = true;char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();} while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();} num = f ? num: -num; }
int out[100];
template<class T> inline
void write(T x,char ch){ if (x==0) {putchar('0'); putchar(ch); return;} if (x<0) {putchar('-'); x=-x;} int num=0; while (x){ out[num++]=(x%10); x=x/10;} fordown(i,num-1,0) putchar(out[i]+'0'); putchar(ch); }
/*========================================================*/
int n,K;
int a[maxn];
int dp[maxn];
bool vis[maxn];
int cnt;
int ans[maxn];
bool check(int x)
{ bool flag=1;
for (int k = 1; k * k - a[x] < N; k++)
{ if (k * k - a[x] <= 0) continue;
if (vis[k * k - a[x]]) {flag = 0;break;}
}
return flag;
}
void cheat1()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check(l)) {vis[a[l]]=1;l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
for ( ; r > l; r--) vis[a[r]] = 0;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
vector<int> g[maxn];
bool sqr[maxn];
int col[maxn];
bool dfs(int x,int f)
{ col[x]=f;
bool flag=1;
for(int i=0;i<g[x].size();i++)
{int u=g[x][i];
if(col[x]==col[u]) {flag=0;break;}
if(col[u]==-1) flag=flag&dfs(u,f^1);
}
return flag;
}
bool check2(int l,int r)
{//cout<<"case"<<endl;
//cout<<l<<' '<<r<<endl;
bool flag=1;
forup(i,l,r)
forup(j,i+1,r)
{//cout<<i<<' '<<j<<endl;
if(sqr[a[i]+a[j]]) g[i].pb(j),g[j].pb(i);
}
forup(i,l,r) col[i]=-1;
forup(i,l,r) if(col[i]==-1) {if(dfs(i,0)==0) {flag=0;break;}}
forup(i,l,r) g[i].clear();
return flag;
}
void cheat2()
{ int r=n,l=n;
while(r)
{int R=r,L=1;
while(L<=R)
{int mid=(L+R)>>1;
if(check2(mid,r)) {l=mid;R=mid-1;}
else {L=mid+1;}
}
l--;
if (!l) break;
ans[++cnt] = l;
r=l;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
int main()
{freopen("division2.in","r",stdin);
//freopen("1.out","w",stdout);
forup(i,1,1000) sqr[i*i]=1;
cin>>n>>K;
forup(i,1,n) read(a[i]);
if(K==1)
{ cheat1();}
if(K==2)
{ cheat2();}
return 0;
}
```
by zhouyihe @ 2017-11-09 20:04:19
```cpp
@[TheUltimateLaw](/space/show?uid=36589) 二分
#include<bits/stdc++.h>
#define pb push_back
#define forup(i,a,b) for(int i=(a);i<=(b);i++)
#define fordown(i,a,b) for(int i=(a);i>=(b);i--)
#define maxn 1000005
#define N 131073
#define INF 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline void read(T& num){ num = 0; bool f = true;char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();} while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();} num = f ? num: -num; }
int out[100];
template<class T> inline
void write(T x,char ch){ if (x==0) {putchar('0'); putchar(ch); return;} if (x<0) {putchar('-'); x=-x;} int num=0; while (x){ out[num++]=(x%10); x=x/10;} fordown(i,num-1,0) putchar(out[i]+'0'); putchar(ch); }
/*========================================================*/
int n,K;
int a[maxn];
int dp[maxn];
bool vis[maxn];
int cnt;
int ans[maxn];
bool check(int x)
{ bool flag=1;
for (int k = 1; k * k - a[x] < N; k++)
{ if (k * k - a[x] <= 0) continue;
if (vis[k * k - a[x]]) {flag = 0;break;}
}
return flag;
}
void cheat1()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check(l)) {vis[a[l]]=1;l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
for ( ; r > l; r--) vis[a[r]] = 0;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
vector<int> g[maxn];
bool sqr[maxn];
int col[maxn];
bool dfs(int x,int f)
{ col[x]=f;
bool flag=1;
for(int i=0;i<g[x].size();i++)
{int u=g[x][i];
if(col[x]==col[u]) {flag=0;break;}
if(col[u]==-1) flag=flag&dfs(u,f^1);
}
return flag;
}
bool check2(int l,int r)
{//cout<<"case"<<endl;
//cout<<l<<' '<<r<<endl;
bool flag=1;
forup(i,l,r)
forup(j,i+1,r)
{//cout<<i<<' '<<j<<endl;
if(sqr[a[i]+a[j]]) g[i].pb(j),g[j].pb(i);
}
forup(i,l,r) col[i]=-1;
forup(i,l,r) if(col[i]==-1) {if(dfs(i,0)==0) {flag=0;break;}}
forup(i,l,r) g[i].clear();
return flag;
}
void cheat2()
{ int r=n,l=n;
while(r)
{int R=r,L=1;
while(L<=R)
{int mid=(L+R)>>1;
if(check2(mid,r)) {l=mid;R=mid-1;}
else {L=mid+1;}
}
l--;
if (!l) break;
ans[++cnt] = l;
r=l;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
int main()
{freopen("division2.in","r",stdin);
//freopen("1.out","w",stdout);
forup(i,1,1000) sqr[i*i]=1;
cin>>n>>K;
forup(i,1,n) read(a[i]);
if(K==1)
{ cheat1();}
if(K==2)
{ cheat2();}
return 0;
}
```
by zhouyihe @ 2017-11-09 20:05:24
```cpp
@[TheUltimateLaw](/space/show?uid=36589) 暴力
#include<bits/stdc++.h>
#define pb push_back
#define forup(i,a,b) for(int i=(a);i<=(b);i++)
#define fordown(i,a,b) for(int i=(a);i>=(b);i--)
#define maxn 1000005
#define N 131073
#define INF 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline void read(T& num){ num = 0; bool f = true;char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();} while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();} num = f ? num: -num; }
int out[100];
template<class T> inline
void write(T x,char ch){ if (x==0) {putchar('0'); putchar(ch); return;} if (x<0) {putchar('-'); x=-x;} int num=0; while (x){ out[num++]=(x%10); x=x/10;} fordown(i,num-1,0) putchar(out[i]+'0'); putchar(ch); }
/*========================================================*/
int n,K;
int a[maxn];
int dp[maxn];
bool vis[maxn];
int cnt;
int ans[maxn];
bool check(int x)
{ bool flag=1;
for (int k = 1; k * k - a[x] < N; k++)
{ if (k * k - a[x] <= 0) continue;
if (vis[k * k - a[x]]) {flag = 0;break;}
}
return flag;
}
void cheat1()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check(l)) {vis[a[l]]=1;l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
for ( ; r > l; r--) vis[a[r]] = 0;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
vector<int> g[maxn];
bool sqr[maxn];
int col[maxn];
bool dfs(int x,int f)
{ col[x]=f;
bool flag=1;
for(int i=0;i<g[x].size();i++)
{int u=g[x][i];
if(col[x]==col[u]) {flag=0;break;}
if(col[u]==-1) flag=flag&dfs(u,f^1);
}
return flag;
}
bool check2(int l,int r)
{//cout<<"case"<<endl;
//cout<<l<<' '<<r<<endl;
bool flag=1;
forup(i,l,r)
forup(j,i+1,r)
{//cout<<i<<' '<<j<<endl;
if(sqr[a[i]+a[j]]) g[i].pb(j),g[j].pb(i);
}
forup(i,l,r) col[i]=-1;
forup(i,l,r) if(col[i]==-1) {if(dfs(i,0)==0) {flag=0;break;}}
forup(i,l,r) g[i].clear();
return flag;
}
void cheat2()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check2(l,r)) {l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
r=l;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
int main()
{freopen("division2.in","r",stdin);
//freopen("1.out","w",stdout);
forup(i,1,1000) sqr[i*i]=1;
cin>>n>>K;
forup(i,1,n) read(a[i]);
if(K==1)
{ cheat1();}
if(K==2)
{ cheat2();}
return 0;
}
```
by zhouyihe @ 2017-11-09 20:05:56