首页 > 代码库 > 水过的题
水过的题
BZOJ 3767: A+B Prlblem加强版:BZOJ 很少见的水题 高精加 python水过
1 a=int(raw_input())2 b=int(raw_input())3 print a+b
BZOJ 3043: IncDec Sequence:差分过后就成了要使差分数列全为0的最小次数,第二问即将差分数列全削成正数或负数后,剩下的操作可以作用在前一段区间,也可以后一段区间,因此会造成不同数列的情况
/************************************************************** Problem: 3043 User: love_zyf Language: C++ Result: Accepted Time:332 ms Memory:2836 kbDescription给定一个长度为n的数列{a1,a2...an},每次可以选择一个区间[l,r],使这个区间内的数都加一或者都减一。问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。Input第一行一个正整数n 接下来n行,每行一个整数,第i+1行的整数表示ai。。Output第一行输出最少操作次数第二行输出最终能得到多少种结果Sample Input41122Sample Output12HINT对于100%的数据,n=100000,0<=ai<2147483648****************************************************************/ //uva#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <queue>#define maxn 100009#define esp 0.001using namespace std;long long a[maxn],b[maxn],c=0,d=0;int main(){ int n; scanf("%d%lld",&n,&a[1]); for(int i=2;i<=n;i++) { scanf("%lld",&a[i]); b[i]=a[i]-a[i-1]; if(b[i]>0)c+=b[i];if(b[i]<0)d-=b[i]; } printf("%lld\n%lld\n",max(c,d),abs(c-d)+1); return 0;}
POJ 2181 Jumping Cows:一开始看错题意,以为是连续的,样例答案怎么也没推出来,看清题意后发现是DP,dp[i][0]表示到第i个数,第i个数是选出的数的奇数项的最大值,dp[i][1]表示使偶数项时的最大值,转移很显然 见代码
1 //dp[i][0]=max(dp[i-1][1]+a[i],a[i]);dp[i][1]=dp[i-1][0]-a[i]; 2 #include <stdio.h> 3 #include <iostream> 4 #include <string.h> 5 #include <algorithm> 6 #include <queue> 7 #define maxn 150090 8 #define esp 0.001 9 #define inf 0x3f3f3f3f10 int max(int x,int y){return x<y?y:x;}11 using namespace std;12 int dp[maxn][2];13 int main()14 {15 int n,x,y,z,ans=0,sign=1;16 scanf("%d",&n);17 for(int i=1;i<=n;i++,sign*=-1)18 {19 scanf("%d",&x);20 dp[i][0]=max(dp[i-1][1]+x,dp[i-1][0]);21 dp[i][1]=max(dp[i-1][1],dp[i-1][0]-x);22 ans=max(ans,max(dp[i][0],dp[i][1]));23 // printf("%d %d\n",dp[i][0],dp[i][1]);24 }25 printf("%d\n",ans);26 return 0;27 }
POJ 1258 Agri-Net:裸MST
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <algorithm> 5 #include <queue> 6 #define maxn 3000 7 #define esp 0.001 8 #define inf 0x3f3f3f3f 9 using namespace std;10 int father[maxn],dis[maxn][maxn];11 struct T12 {13 int x;14 int y;15 int v;16 }a[maxn*1000];17 int cmp(T x,T y)18 {19 return x.v<y.v;20 }21 int find(int x)22 {23 if(x==father[x])return x;24 return father[x]=find(father[x]);25 }26 int main()27 {28 int n,i;29 while(scanf("%d",&n)!=EOF)30 {31 int h=0,ans=0;32 for(i=1;i<=n;i++)father[i]=i;33 for(i=1;i<=n;i++)34 {35 for(int j=1;j<=n;j++)scanf("%d",&dis[i][j]);36 }37 for(int i=1;i<=n;i++)38 {39 for(int j=1;j<i;j++)if(dis[i][j]!=0)40 {41 a[++h].x=i;42 a[h].y=j;43 a[h].v=dis[i][j];44 }45 }46 sort(a+1,a+1+h,cmp);47 for(i=1;i<=h;i++)48 {49 int xx=find(a[i].x),yy=find(a[i].y);50 if(xx!=yy)51 {52 father[xx]=yy;53 ans+=a[i].v;54 }55 }56 printf("%d\n",ans);57 }58 return 0;59 }
POJ 1251 Jungle Roads:同上 裸MST
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <algorithm> 5 #include <queue> 6 #define maxn 100009 7 #define esp 0.001 8 #define inf 0x3f3f3f3f 9 using namespace std;10 int h,father[maxn];11 int find(int x)12 {13 if(x==father[x])return x;14 return father[x]=find(father[x]);15 }16 struct T{int x;int y;int v;}a[maxn];17 int cmp(T x,T y){return x.v<y.v;}18 int main()19 {20 int n,i;21 char ch[10],ch2[10];22 while (1)23 {24 h=0;25 int ans=0,m,x;26 scanf("%d",&n);27 if(n==0)break;28 for(int i=1;i<=n;i++)father[i]=i;29 for(i=1;i<=n-1;i++)30 {31 scanf("%s%d",ch,&m);32 for(int j=1;j<=m;j++)33 {34 scanf("%s%d",ch2,&x);35 a[++h].x=(int)ch[0]-‘A‘+1;36 a[h].y=(int)ch2[0]-‘A‘+1;37 a[h].v=x;38 }39 }40 sort(a+1,a+1+h,cmp);41 for(i=1;i<=h;i++)42 {43 int xx=find(a[i].x),yy=find(a[i].y);44 if(xx!=yy)45 {46 ans+=a[i].v;47 father[xx]=yy;48 }49 }50 printf("%d\n",ans);51 }52 return 0;53 }
水过的题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。