决赛,我自我认为题目难度更大,反而我的心态更好了。
由于放轻松的时候反而效果更好,跟昨天的观点一样,凡是可以1A的,才算这题做得好。
A.数目不大,关键是看懂题(我自己连输入输出是什么都不清楚。。。。
然后管理员就把题下掉了。
。
。。批评批评啊。
。。
)bin神的代码膜拜了下。知道是状态压缩,题中说了最多6个,要么1<<6枚举,要么6!枚举。代码:
/* *********************************************** Author :kuangbin Created Time :2015/3/15 14:17:30 File Name :GDUT\A.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int INF = 0x3f3f3f3f; int dp[1000]; int st[6410],cost[6410]; int num[6410]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); int cnt = 0; for(int i = 0;i < n;i++){ int m; int nn; int p; scanf("%d%d",&m,&nn); while(m--){ int k; scanf("%d",&k); st[cnt] = 0; num[cnt] = nn; while(k--){ scanf("%d",&p); st[cnt] |= (1<<p); } scanf("%d",&cost[cnt]); cnt++; } } for(int i = 0;i < (1<<6);i++)dp[i] = INF; dp[0] = 0; for(int i = 0;i < (1<<6);i++){ if(dp[i] == INF)continue; for(int j = 0;j < cnt;j++){ if( (i&(1<<num[j])) != 0)continue; if( (i|st[j]) != i )continue; dp[i|(1<<num[j])] = min(dp[i|(1<<num[j])],dp[i]+cost[j]); } } int tot = (1<<6)-1; if(dp[tot] == INF)dp[tot] = -1; printf("%d\n",dp[tot]); } return 0; }
B.区间DP,因为是随意地方插入0或者1,那么单位长度显然ans为0。两个长度作为初始化推断。然后区间DP
代码:
/* *********************************************** Author :kuangbin Created Time :2015/3/15 13:05:55 File Name :GDUT\B.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; char str[1010]; int a[1010]; int dp[1010][1010]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T; int n; scanf("%d",&T); while(T--){ scanf("%d",&n); scanf("%s",str); for(int i = 0;i < n;i++) a[i] = str[i]-'0'; memset(dp,0,sizeof(dp)); for(int i = 0;i < n;i++) dp[i][i] = 1; for(int i = n-1;i >= 0;i--) for(int j = i+1;j < n;j++){ dp[i][j] = j-i+1; if(a[i] != a[j]) dp[i][j] = min(dp[i][j],dp[i+1][j-1]); dp[i][j] = min(dp[i][j],dp[i+1][j]+1); dp[i][j] = min(dp[i][j],dp[i][j-1]+1); } printf("%d\n",dp[0][n-1]); } return 0; }
C.这道题表述上事实上是没有问题的,可是大家会陷于自己生活中的误区,菜怎么可能炒到一半就换种菜?这个题的第一组数据是个非常经典的小学竞赛问题:2个锅,要做出来3个饼,每一个饼须要2分钟做好,问你最少几分钟能够做好?答案是3.过程是这样:第一分钟,做第1和2个饼;第二分钟,做第2和3个饼。第三分钟,做1和3个饼。
那么,非常明显:利用的贪心思想。
把全部的饼尽可能的分到不同的锅里去。
那么就是取平均值的上整数值。可是一个菜不能分成多份,那么就是要统计出最大值,于是,求得就是平均值的上整数值和最大值的较大值。绕口,可是代码非常好懂
#include <iostream> #include <algorithm> #include <stdio.h> #include <math.h> #include <map> #include <set> #include <vector> #include <string> #include <cstring> #include <sstream> #include <queue> #include <stack> using namespace std; #define input freopen("input.txt","r",stdin) #define output freopen("output.txt","w",stdout) #define For1(i,a,b) for (i=a;i<b;i++) #define For2(i,a,b) for (i=a;i<=b;i++) #define Fill(x,a) memset(x,a,sizeof(x)) #define inf 99999999 #define pi 3.1415926535897932384626433832795028841971 int main(){ int t,n,m; int Max,aver,num; scanf("%d",&t); while(t--){ aver=Max=0; scanf("%d%d",&n,&m); while(n--){ scanf("%d",&num); Max=max(Max,num); aver+=num; } aver=(aver+m-1)/m; printf("%d\n",max(aver,Max)); } return 0; }
D.数学题。
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<set> #include<iostream> using namespace std; typedef long long LL; LL n, m; LL Gcd(LL x, LL y) { if (!y) return x; else return Gcd(y, x%y); } LL solve(LL n) { LL sum = 0; LL i, j; for (i = 1; i <= (double)sqrt(n*1.0); i++) { if (n%i==0) { j = n / i; if (Gcd(i, j) == 1) ++sum; } } return sum; } int main() { int T, i, Case = 0, j, k; //freopen("data.txt", "r", stdin); scanf("%d", &T); while (T--) { scanf("%lld%lld", &n, &m); if (m%n) { printf("0\n"); continue; } LL temp = m / n; printf("%lld\n", solve(temp)); } return 0; }
原因就是太过于自信。我的找爸爸直接用的fa[i]而不是getf[i]。
。。。。哭死。
。。
。
有些细节问题,不要一直提交的啊。。能够先做做别的题冷静冷静,或者自己写几个測试数据,检測下。20分钟罚时非常多的啊
#include <iostream> #include <algorithm> #include <stdio.h> #include <math.h> #include <map> #include <set> #include <vector> #include <string> #include <cstring> #include <sstream> #include <queue> #include <stack> using namespace std; #define input freopen("input.txt","r",stdin) #define output freopen("output.txt","w",stdout) #define For1(i,a,b) for (i=a;i<b;i++) #define For2(i,a,b) for (i=a;i<=b;i++) #define Fill(x,a) memset(x,a,sizeof(x)) #define inf 99999999 #define pi 3.1415926535897932384626433832795028841971 const long long maxn=1000050; int t; long long n,m; long long fa[maxn]; void init(){ for(long long i=0;i<=n;i++) fa[i]=i; } long long getf(long long x){ if (fa[x]==x) return x; return fa[x]=getf(fa[x]); } int main(){ input; long long i,j,k; scanf("%d",&t); while(t--){ scanf("%lld%lld",&n,&m); init(); while(m--){ scanf("%lld",&i); scanf("%lld",&j); long long fi=getf(i); long long fj=getf(j); if (fi!=fj) fa[fi]=fj; } k=0; long long f1=getf(1); for(i=2;i<=n;i++){ int fi=getf(i); if (fi!=f1){ fa[fi]=f1; k++; } } printf("%lld\n",k); } return 0; }
依照题目的意思来呗。
要你干啥就干啥。推断n和m仅仅有100怎么循环都只是分的
#include <iostream> #include <algorithm> #include <stdio.h> #include <math.h> #include <map> #include <set> #include <vector> #include <string> #include <cstring> #include <sstream> #include <queue> #include <stack> using namespace std; #define input freopen("input.txt","r",stdin) #define output freopen("output.txt","w",stdout) #define For1(i,a,b) for (i=a;i<b;i++) #define For2(i,a,b) for (i=a;i<=b;i++) #define Fill(x,a) memset(x,a,sizeof(x)) #define inf 99999999 #define pi 3.1415926535897932384626433832795028841971 int vis[200]; int num[200]; int main(){ //input; int t; int n,m; int i,j,k; scanf("%d",&t); while(t--){ memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d",&num[i]); for(i=1;i<=m;i++) for(j=1;j<=n;j++){ if (vis[j]) continue; if (j>=num[i]) vis[j]=num[i]; } for(i=1;i<=n;i++) printf("%d%c",vis[i],i==n?'\n':' '); } return 0; }
看到那么大的n心里就不要慌啊,肯定是有规律的啊。肯定是不能打表的啊,肯定是小数据猜过程猜结论的啊
或者写出这个数列:1 3 6 10 15 21 28 36 45 55 66 78……
看到规律了吗?每三个数一组,每组的第一个不是3的倍数,第二个和第三个是3的倍数。程序大家自己写吧
H.DP。我最高兴的是这道题我的思路跟bin神是一样的啊,说明有些题是能够做的啊,不要自己吓自己的,比方BC33的第3题。我看着是状态压缩。。赛后理解就是个复杂一点的背包。。(扯远了。。)
定义:dp[i][j][k]代表第一个手指在i处。第二个手指在j处,当前已经完毕k格走过的最短距离。0<=i<=4,0<=j<=4,1<=k<=n。
依据题中数据,n最大10000。
放心的一次循环解决。
初始值为-1意味着当前情况取不到(非经常见的思路啊,用-1标记不可达,用正数标记最短路),初始情况呢,dp[0][0][0]=0
递推的思路也非常easy:假设新节点没去过(值为-1),去呗。去过的话,取小值呗
代码例如以下:
#include <iostream> #include <algorithm> #include <stdio.h> #include <math.h> #include <map> #include <set> #include <vector> #include <string> #include <cstring> #include <sstream> #include <queue> #include <stack> using namespace std; #define input freopen("input.txt","r",stdin) #define output freopen("output.txt","w",stdout) #define For1(i,a,b) for (i=a;i<b;i++) #define For2(i,a,b) for (i=a;i<=b;i++) #define Fill(x,a) memset(x,a,sizeof(x)) #define inf 99999999 #define pi 3.1415926535897932384626433832795028841971 int dp[10][10][10050]; int t,n; int num[10050]; int main(){ int i,j,k,dis; scanf("%d",&t); while(t--){ scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&num[i]); memset(dp,-1,sizeof(dp)); dp[0][0][0]=0; for(k=1;k<=n;k++) for(i=0;i<=4;i++) for(j=0;j<=4;j++){ if (dp[i][j][k-1]==-1) continue; dis=abs(i-num[k]); if (dp[num[k]][j][k]==-1) dp[num[k]][j][k]=dp[i][j][k-1]+dis; else dp[num[k]][j][k]=min(dp[num[k]][j][k],dp[i][j][k-1]+dis); dis=abs(j-num[k]); if (dp[i][num[k]][k]==-1) dp[i][num[k]][k]=dp[i][j][k-1]+dis; else dp[i][num[k]][k]=min(dp[i][num[k]][k],dp[i][j][k-1]+dis); } int ans=100000000; for(i=0;i<=4;i++) for(j=0;j<=4;j++) if (dp[i][j][n]!=-1&&dp[i][j][n]<ans) ans=dp[i][j][n]; printf("%d\n",ans); } return 0; }
原文:http://www.cnblogs.com/cynchanpin/p/7261382.html