A.hdu1003 Max Sum
dp求最大序列和
dp[i] = max(dp[i-1],0)+a[i] ps.dp[i]当前元素结尾的最大序列和
mmax = max(mmax,dp[i])
讲的不清楚，可以看看别人的思路
http://alorry.blog.163.com/blog/static/6472570820123801223397/
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int MAXN = 1e5+100; const int inf = 0x3f3f3f3f; int a[MAXN],dp[MAXN]; int main(){ int T; scanf("%d",&T); int mc = 0; while(T--){ int n; scanf("%d",&n); int mmax = -inf,l,r,t; l = r = 1; dp[0] = -1; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(dp[i-1]>=0){ dp[i] = dp[i-1]+a[i]; //mmax = max(mmax,dp[i]); }else{ t = i; dp[i] = a[i]; } if(mmax<dp[i]){ mmax = dp[i]; l = t; r = i; } } printf("Case %d: %d %d %d ",++mc,mmax,l,r); if(T)cout<<endl; } return 0; }
B.hdu2522 A simple problem
求小数循环节的思路可以看看这个链接
http://www.cnblogs.com/hxsyl/p/3330481.html
1/n的循环节最多有(n-1)个数，只要用长除法得到第一次余数重复，前面的的商就是答案
n也可以是负数
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int MAXN = 1e5+100; int mark[MAXN]; int ans[MAXN]; int top,l; void solve(int x){ memset(mark,0,sizeof mark); top = l = 0; int s = 1,t; mark[1] = 1; while(s){ t = s*10/x; s = s*10%x; ans[top++] = t; if(mark[s]){ break; } mark[s] = 1; } } int main() { int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); if(n<0){cout<<"-";n = fabs(n);} if(n==1){ cout<<1<<endl; continue; } solve(n); if(n==1){ cout<<0<<endl; continue; } cout<<"0."; for(int i=0;i<top;i++)cout<<ans[i]; cout<<endl; } //cout << "Hello world!" << endl; return 0; }
C.hdu1506 Largest Rectangle in a Histogram
题意:从左到右，对于每个点，记算出他所能向左和向右延伸的最大边界，该长度乘以该点高度就是该点所能呈现的最大值，最后扫描一边找出最大的
比如2 4 3 4 2 4 ,a3(3)能向左延伸1，向右延伸3，所以a3所能代表的矩阵就是(1+1+3)*3
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long long ll; const int MAXN = 1e5+100; const int inf = 0x3f3f3f3f; int a[MAXN],L[MAXN],R[MAXN]; int main(){ int n; while(scanf("%d",&n)!=EOF&&n){ for(int i=1;i<=n;i++){scanf("%d",&a[i]);L[i] = R[i] = i;} for(int i=1;i<=n;i++){ int t = i; while(t>=1&&a[i]<=a[t]){ L[i] = L[t]; t = L[t]-1; } } for(int i=n;i>=1;i--){ int t = i; while(t<=n&&a[i]<=a[t]){ R[i] = R[t]; t = R[t]+1; } } ll mmax = -inf; for(int i=1;i<=n;i++){ mmax = max(mmax,(1LL)*a[i]*(R[i]-L[i]+1)); } cout<<mmax<<endl; } return 0; }
D.poj3047 Bovine Birthday
求任意给定日期的是星期几
蔡勒公式套一下就可以了
#include <iostream> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; /*计算任何日期为周几模板*/ int fun(int x,int y,int z){ if(y<3){ x-=1; y+=12; } int a = x/100,b = x-100*a; int w = a/4 - 2*a+b+b/4+(13*(y+1)/5)+z-1; w = (w%7+7)%7; return w; } int main() { /*for(int i=1;i<13;i++){ cout<<fun(2016,i,1)<<" "; } cout<<endl;*/ int x,y,z; while(scanf("%d%d%d",&x,&y,&z)!=EOF){ int w = fun(x,y,z); if(w==1)cout<<"monday"<<endl; else if(w==2)cout<<"tuesday"<<endl; else if(w==3)cout<<"wednesday"<<endl; else if(w==4)cout<<"thursday"<<endl; else if(w==5)cout<<"friday"<<endl; else if(w==6)cout<<"saturday"<<endl; else cout<<"sunday"<<endl; } //cout << "Hello world!" << endl; return 0; }
E.hdu1232 畅通工程
最小生成树模板套一下就可以了
http://www.cnblogs.com/EdsonLin/p/5586034.html
F.poj2603 Brave balloonists
10个数的乘积sa 的所有因子个数(包括它本身)
思路:先将一个数可以化做素数的乘积形式
比如60 = 2^2 * 3^1 * 5^1
这样'2'可以提供(0,1,2)个2，'3'可以提供（0,1）个3，'5'可以提供（0，1）个5
所以60的所有因子个数就是 (2+1)*(1+1)*(1+1),ps.如果不包括本身的化最后要减去1
先打素数表，标记每个素数的个数，然后就可以得到答案
这题也是上一次的校赛题。。。
#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int MAXN = 1e4+100; int a[10]; int p[MAXN],vis[MAXN],num[MAXN]; int cnt; void isprime(){ cnt = 0; for(int i=2;i<MAXN;i++){ if(!vis[i]){ p[cnt++] = i; for(int j=i*2;j<MAXN;j+=i){ vis[j] = 1; } } } } int main(){ isprime(); // for(int j=0;j<5;j++)cout<<p[j]<<" "; // cout<<endl; for(int i=0;i<10;i++)scanf("%d",&a[i]); //int sum = 0; for(int i=0;i<10;i++){ int t = a[i],k; for(int j=0;j<cnt&&p[j]<=t;j++){ k = 0; if(t%p[j]==0){ while(t%p[j]==0){ t/=p[j]; k++; } num[j] += k; //cout<<p[j]<<" "; } } } int sum = 1; for(int j=0;j<cnt;j++){ if(num[j]){ sum *= (1+num[j]); sum %= 10; } } //sum = (sum-1+10)%10; cout<<sum<<endl; return 0; }
G.hdu1563 Find your present!
题意：如果某个数只有奇数个，那这个数就是特殊数，输出这个数，本题应该只存在一个这样的数
可以用因为输入的数可能比较大，用数组下标表示的话会爆数组，可以用c++的map
还有一种方法是用异或 比如 3^5^3^4^4^4^4 最后结果就是3,将该序列异或，最后剩余的结果就是答案
#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int MAXN = 2e2+100; int a[MAXN]; int main(){ int n; while(scanf("%d",&n)!=EOF&&n){ int ans = 0; for(int i=0;i<n;i++){ scanf("%d",&a[i]); ans ^= a[i]; } cout<<ans<<endl; } return 0; }
H. hud3351 Seinfeld
题意:给定一个括号序列，可以改变任意括号的方向，要求改变的数目最少，最后使得这个序列的括号完全配对 ps.题目给的序列应该就是偶数的
思路：括号配对应该想到栈操作，比如比如输入{ { { { } { } } { } } { , 自己模拟这个过程，按顺序压入栈中，如果栈顶top是{，当前i要压入的的是 }，则说明这两个已经匹配，将栈顶元素弹出，当前元素变为i+1
同颜色消除就是这个过程
最后在栈里面的元素必然只有两种情况
1.{{{{{{{ 全部都为{
2.}}}}{{{{{{{ 靠栈底都是} 靠栈底都是{
t1表示}个数 t2表示{个数
则最后最小的改变数量是sum = (t1+1)/2+(t2+1)2
ps.t1为奇数 t2必然也为奇数
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <string> #include <stack> #include <queue> const int inf = (1<<31)-1; const int MAXN = 1e5+10; using namespace std; stack<char>a; int main() { string s1; int mc=1; while(cin>>s1&&s1[0]!='-'){ int n = s1.length(); for(int i=0;i<n;i++){ if(a.empty()){ a.push(s1[i]); }else{ if(a.top()=='{'&&s1[i]=='}') a.pop(); else a.push(s1[i]); } } int t1,t2; t1 = t2 = 0; while(!a.empty()){ if(a.top()=='{') t1++; else t2++; a.pop(); } cout<<mc++<<". "; cout<<(t1+1)/2+(t2+1)/2<<endl; } //cout << "Hello world!" << endl; return 0; }
I.poj1088 滑雪
dp+dfs 找到最长递减序列
dp[i][j] = max(dp[i-1][j],dp[i+1][j-1],d[i][j-1],dp[i][j+1]
J. uva1416 Warfare And Logistics
构造单源最短路径树