BZOJ3275: Number

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #include<string>
12 #define inf 1000000000
13 #define maxn 3000+10
14 #define maxm 10000000
15 #define eps 1e-10
16 #define ll long long
17 #define pa pair<int,int>
18 #define for0(i,n) for(int i=0;i<=(n);i++)
19 #define for1(i,n) for(int i=1;i<=(n);i++)
20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
22 #define mod 1000000007
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}
29     return x*f;
30 }
31 int  n,m,s,t,tot=1,head[maxn],cur[maxn],h[maxn],q[maxn],a[maxn];
32 ll sum,maxflow;
33 struct edge{int go,next,v;}e[maxm];
34 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;}
35 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);}
36 bool bfs()
37 {
38     for(int i=s;i<=t;i++)h[i]=-1;
39     int l=0,r=1;q[1]=s;h[s]=0;
40     while(l<r)
41     {
42         int x=q[++l];
43         for(int i=head[x];i;i=e[i].next)
44          if(e[i].v&&h[e[i].go]==-1)
45          {
46             h[e[i].go]=h[x]+1;q[++r]=e[i].go;
47          }
48     }
49     return h[t]!=-1;
50 }
51 int dfs(int x,int f)
52 {
53     if(x==t) return f;
54     int tmp,used=0;
55     for(int i=cur[x];i;i=e[i].next)
56      if(e[i].v&&h[e[i].go]==h[x]+1)
57     {
58         tmp=dfs(e[i].go,min(e[i].v,f-used));
59         e[i].v-=tmp;if(e[i].v)cur[x]=i;
60         e[i^1].v+=tmp;used+=tmp;
61         if(used==f)return f;
62     }
63     if(!used) h[x]=-1;
64     return used;
65 }
66 void dinic()
67 {
68     maxflow=0;
69     while(bfs())
70     {
71         for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=(ll)dfs(s,inf);
72     }
73 }
74 inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
75 int main()
76 {
77     freopen("input.txt","r",stdin);
78     freopen("output.txt","w",stdout);
79     n=read();s=0;t=n+1;
80     for1(i,n)
81     {
82         int x=a[i]=read();sum+=(ll)x;
83         if(x&1)insert(s,i,x);else insert(i,t,x);
84     }
85     for1(i,n)for1(j,n)
86     if((a[i]&1)&&(!(a[j]&1))&&(gcd(a[i],a[j])==1))
87     {
88         ll x=(ll)a[i]*(ll)a[i]+(ll)a[j]*(ll)a[j],y=sqrt(x);
89         if(y*y!=x)continue;
90         insert(i,j,inf);
91     }
92     dinic();
93     cout<<sum-maxflow<<endl;
94     return 0;
95 }

3275: Number

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 372  Solved: 153
[Submit][Status]

Description

有N个正整数,需要从中选出一些数,使这些数的和最大。
若两个数a,b同时满足以下条件,则a,b不能同时被选
1:存在正整数C,使a*a+b*b=c*c
2:gcd(a,b)=1

Input

第一行一个正整数n,表示数的个数。

第二行n个正整数a1,a2,?an。

Output

最大的和。

Sample Input

5
3 4 5 6 7

Sample Output

22

HINT

n<=3000。

题解:

被精度卡了1h+各种酸爽。。。

我居然没发现奇数之间不满足条件1,orz。

奇数的平方和%4=2,而平方数%4=0/1 so。。。

这是个二分图。

s->奇数 连该数的权

偶数->t 连该数的权

然后如果a[i],a[j]满足条件连边i->j inf

然后用sum-最小割。

因为在最小割中,连边inf的意为a[i]与a[j]必须在同一割中,然后就是损失了某个的权值,正好对应了扣分。

代码:

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #include<string>
12 #define inf 1000000000
13 #define maxn 3000+10
14 #define maxm 10000000
15 #define eps 1e-10
16 #define ll long long
17 #define pa pair<int,int>
18 #define for0(i,n) for(int i=0;i<=(n);i++)
19 #define for1(i,n) for(int i=1;i<=(n);i++)
20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
22 #define mod 1000000007
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}
29     return x*f;
30 }
31 int  n,m,s,t,tot=1,head[maxn],cur[maxn],h[maxn],q[maxn],a[maxn];
32 ll sum,maxflow;
33 struct edge{int go,next,v;}e[maxm];
34 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;}
35 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);}
36 bool bfs()
37 {
38     for(int i=s;i<=t;i++)h[i]=-1;
39     int l=0,r=1;q[1]=s;h[s]=0;
40     while(l<r)
41     {
42         int x=q[++l];
43         for(int i=head[x];i;i=e[i].next)
44          if(e[i].v&&h[e[i].go]==-1)
45          {
46             h[e[i].go]=h[x]+1;q[++r]=e[i].go;
47          }
48     }
49     return h[t]!=-1;
50 }
51 int dfs(int x,int f)
52 {
53     if(x==t) return f;
54     int tmp,used=0;
55     for(int i=cur[x];i;i=e[i].next)
56      if(e[i].v&&h[e[i].go]==h[x]+1)
57     {
58         tmp=dfs(e[i].go,min(e[i].v,f-used));
59         e[i].v-=tmp;if(e[i].v)cur[x]=i;
60         e[i^1].v+=tmp;used+=tmp;
61         if(used==f)return f;
62     }
63     if(!used) h[x]=-1;
64     return used;
65 }
66 void dinic()
67 {
68     maxflow=0;
69     while(bfs())
70     {
71         for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=(ll)dfs(s,inf);
72     }
73 }
74 inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
75 int main()
76 {
77     freopen("input.txt","r",stdin);
78     freopen("output.txt","w",stdout);
79     n=read();s=0;t=n+1;
80     for1(i,n)
81     {
82         int x=a[i]=read();sum+=(ll)x;
83         if(x&1)insert(s,i,x);else insert(i,t,x);
84     }
85     for1(i,n)for1(j,n)
86     if((a[i]&1)&&(!(a[j]&1))&&(gcd(a[i],a[j])==1))
87     {
88         ll x=(ll)a[i]*(ll)a[i]+(ll)a[j]*(ll)a[j],y=sqrt(x);
89         if(y*y!=x)continue;
90         insert(i,j,inf);
91     }
92     dinic();
93     cout<<sum-maxflow<<endl;
94     return 0;
95 }

还有以后判断是否是平方数一定这样写!!!开long long!!!

  ll y=sqrt(x);
  return y*y==x;
时间: 12-12

BZOJ3275: Number的相关文章

[BZOJ3275] Number (网络流)

Description 有N个正整数,需要从中选出一些数,使这些数的和最大. 若两个数a,b同时满足以下条件,则a,b不能同时被选 1:存在正整数C,使a*a+b*b=c*c 2:gcd(a,b)=1 Input 第一行一个正整数n,表示数的个数. 第二行n个正整数a1,a2,?an. Output 最大的和. Sample Input 5 3 4 5 6 7 Sample Output 22 HINT n<=3000. Source 网络流 Solution 所以这道题a的数据范围是什么...

【BZOJ-3275&amp;3158】Number&amp;千钧一发 最小割

3275: Number Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 748  Solved: 316[Submit][Status][Discuss] Description 有N个正整数,需要从中选出一些数,使这些数的和最大.若两个数a,b同时满足以下条件,则a,b不能同时被选1:存在正整数C,使a*a+b*b=c*c2:gcd(a,b)=1 Input 第一行一个正整数n,表示数的个数. 第二行n个正整数a1,a2,?an. Output

Codeforces 124A - The number of positions

题目链接:http://codeforces.com/problemset/problem/124/A Petr stands in line of n people, but he doesn't know exactly which position he occupies. He can say that there are no less than a people standing in front of him and no more than b people standing b

17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Input:Digit string "23" Output: ["ad", "ae", &q

实现一个函数clone,使JavaScript中的5种主要的数据类型(包括Number、String、Object、Array、Boolean)进行值复制

实现一个函数clone,可以对JavaScript中的5种主要的数据类型(包括Number.String.Object.Array.Boolean)进行值复制. 1 /** 对象克隆 2 * 支持基本数据类型及对象 3 * 递归方法 */ 4 function clone(obj) { 5 var o; 6 switch (typeof obj) { 7 case "undefined": 8 break; 9 case "string": o = obj + &q

解决sqoop报错Invalid number; item = ITEM_UNICODE

报错栈: java.sql.SQLException: Invalid number; item = ITEM_UNICODE at com.intersys.jdbc.SysList.getInt(SysList.java:1735) at com.intersys.jdbc.CacheResultSet.getInt(CacheResultSet.java:247) at org.apache.sqoop.lib.JdbcWritableBridge.readInteger(JdbcWrit

1005 Number Sequence

Problem Description A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n). Input The input consists of multiple test cases. Each test case co

Minimum Inversion Number 【线段数】

Problem DescriptionThe inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj. For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of

171. Excel Sheet Column Number

Excel Sheet Column Number Related to question Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 static publi