1 /* 2     尽管是网络流24题之一  3     我还是忍不住用了贪心  4 */ 5 #include <cmath> 6 #include <ctype.h> 7 #include <cstdio> 8  9 const int MAXN=1010;10 11 int tot,n;12 13 int a[MAXN][MAXN];14 15 inline void read(int&x) {16     register char c=getchar();17     for(x=0;!isdigit(c);c=getchar());18     for(;isdigit(c);x=x*10+c-48,c=getchar());19 }20 21 inline bool check(int x) {22     int p=sqrt(x);23     if(p*p==x) return true;24     else return false;25 }26 27 int hh() {28     freopen("balla.in","r",stdin);29     freopen("balla.out","w",stdout);30     read(n);31     int it=1;32     a[++tot][++a[tot][0]]=1;33     while(true) {34         int flag=0;++it;35         for(int i=1;i<=tot;++i) {36             int t=it+a[i][a[i][0]];37             if(check(t)) a[i][++a[i][0]]=it,flag=1;38             if(flag) break;39         }40         if(flag) continue;41         tot++;42         a[tot][++a[tot][0]]=it;43         if(tot>n) break;44     }45     printf("%d\n",it-1);46 /*    for(int i=1;i<tot;++i) {47         for(int j=1;j<=a[i][0];++j)48           printf("%d ",a[i][j]);49         printf("\n");50     }*/51     return 0;52 } 53 54 int sb=hh();55 int main() {;}

 1 /* 2     二分图匹配  3 */ 4 #include <cstdio> 5 #include <cstring>  6  7 const int MAXN=4001; 8 const int MAXM=30010; 9 10 int n,mark[MAXM],vist[MAXM];11 12 bool c[MAXN],vis[MAXN];13 14 struct PLU {15     int to;16     int next;17 };18 PLU t[MAXM];19 20 int head[MAXN],tot=1;21 22 inline void add(int x,int y) {23     t[++tot].to=y;24     t[tot].next=head[x];25     head[x]=tot; 26 } 27 28 bool find(int x) {29     for(int i=head[x];i!=-1;i=t[i].next) {30         int to=t[i].to;31         if(!vis[to]) {32             vis[to]=true;33             if(!mark[to]||find(mark[to])) {34                 vist[x]=to,mark[to]=x;35                 return true;36             }37         } 38     }39     return false;40 }41 42 int hh() {43     freopen("balla.in","r",stdin);44     freopen("balla.out","w",stdout);45     int ans=0;46     scanf("%d",&n);47     memset(head,-1,sizeof head);48     for(int i=1;i<=63;++i) c[i*i]=true;49     for(int i=1;i<=1600;++i) {50         for(int j=1;j<i;++j)51             if(c[i+j]) add(i,j);52         for(int j=1;j<=i;++j) {53             if(!vist[j]) {54                 memset(vis,false,sizeof vis);55                 if(find(j)) ++ans;56             } 57         }58         if(i-ans>n) {59             printf("%d\n",i-1);60             goto END; 61         } 62     }63 END:64     return 0;65 }66 67 int sb=hh();68 int main() {;}

  1 /*  2     对于每一个 x+y=i^2(x<y)  3     依照题意我们知道 x,y 都能且只能使用一次  4     所以我们可以把每一个数字 x 拆成 x1 和 x0  5     其中 x1 加上一个比 x1 小的数字构成一个完全平方数  6     x0 加上一个比 x0 大的数构成一个完全平方数  7     再把所有的 (y0,z1)(y0+z1=i^2,y0<z1,i∈N+)   8     之间连一条有向边就是一个二分图匹配的问题了  9      10     新增一个源 S 和汇 T  11     把当前的整数 x 拆成 x0 和 x1  12     连接一条容量为 1   从 S 到 x0 的有向边  13     连接一条容量为 1   从 x1 到 T 的有向边  14      连接一条容量为 1   从 x0 到 k(x0+k=i^2,k∈N+,i∈N+) 的有向边 15 */ 16 #include <queue> 17 #include <cmath> 18 #include <cstring> 19 #include <cstdio> 20  21 const int MAXN=40010; 22 const int INF=0x7fffffff; 23  24 struct data { 25     int to; 26     int next; 27     int val; 28 };  29 data e[MAXN]; 30  31 int head[MAXN],cur[MAXN],tot=1; 32  33 int depth[MAXN]; 34  35 int src,decc,n; 36  37 std::queue<int>q; 38  39 inline void add(int x,int y,int z) { 40     e[++tot].to=y; 41     e[tot].val=z; 42     e[tot].next=head[x]; 43     head[x]=tot; 44 } 45  46 inline int min(int a,int b) { 47     return a<b?a:b; 48 }  49  50 bool bfs() { 51     for(int i=0;i<=decc;++i) cur[i]=head[i],depth[i]=-1; 52     while(!q.empty()) q.pop(); 53     q.push(src); 54     depth[src]=0; 55     while(!q.empty()) { 56         int u=q.front();  57         q.pop(); 58         for(int i=head[u];i!=-1;i=e[i].next) { 59             int to=e[i].to; 60             if(e[i].val&&depth[to]==-1) { 61                 depth[to]=depth[u]+1; 62                 q.push(to); 63                 if(to==decc) return true; 64             } 65         } 66     } 67     return false; 68 } 69  70 int dfs(int now,int flow) { 71     if(now==decc) return flow; 72     int used=0,delat; 73     for(int & i=cur[now];i!=-1;i=e[i].next) { 74         int to=e[i].to; 75         if(e[i].val&&depth[to]==depth[now]+1) { 76             delat=flow-used; 77             delat=dfs(to,min(delat,e[i].val)); 78             e[i].val-=delat; 79             e[i^1].val+=delat; 80             used+=delat; 81             if(used==flow) break;  82         } 83     } 84     if(!used) depth[now]=-1; 85     return used; 86 } 87  88 int hh() { 89     freopen("balla.in","r",stdin); 90     freopen("balla.out","w",stdout); 91     int ans=0,it=0; 92     memset(head,-1,sizeof head); 93     decc=1610*2; 94     scanf("%d",&n); 95     while(true) { 96         ++ans,++it; 97         for(int i=1;i<it;++i) 98           if(sqrt(i+it)==int(sqrt(i+it)))  99             add(i,it+1600,1),add(it+1600,i,0);100         add(src,it,1);add(it,src,0);101         add(it+1601,decc,1);add(decc,it+1601,0);102         while(bfs())103           ans-=dfs(src,INF);104         if(ans>n) break;105     }106     printf("%d\n",it-1);107     return 0;108 }109 110 int sb=hh();111 int main() {;}