首页 > 代码库 > 水过的题

水过的题

BZOJ 3767: A+B Prlblem加强版:BZOJ 很少见的水题 高精加 python水过

1 a=int(raw_input())2 b=int(raw_input())3 print a+b
View Code

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;}
View Code

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 }
View Code

 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 }
View Code

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 }
View Code

 

水过的题