时间：2017年2月3号
总结：题目偏简单。不过可能是最近囫囵吞枣般地学了太多算法，自己做题时的脑洞越来越少......有时明明很简单的题却总想往学过的算法上面靠....浪费了很多时间，虽然能AC，但效率低了很多。
改进：补完以前剩下的hdoj11页的水题，另外做题时学会从多个角度去思考以找到解题的思路。
题目：
1001:
abcdABCDabCDSample Output
042签到题#include <bits/stdc++.h>using namespace std;typedef long long ll;char str[1010];int main(){ while(scanf("%s",str) != EOF){ int len = strlen(str); int ans = 0; for(int i=0 ;i<len ;i++){ if(str[i]>='A' && str[i]<='Z') ans++; } printf("%d/n",ans); } return 0;}1002:Problem B XRT in FSK
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 100 Accepted Submission(s) : 36
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
由于学校的实习安排，XRT被安排去了烟台FSK当质检工(XRT:为什么是我...)。每次XRT都要检查n个小球，已知这n个小球里面有一个是比较轻的，其余的n-1个小球重量都相同。XRT有一个天平，每次他可以把若干个球放在左边，若干个球放在右边，然后得到结果：左边重，右边重和平衡。由于XRT的数学很弱（XRT：泥垢了....），所以你可以告诉他,最少测量多少次能保证把比较轻的小球找出来吗?Input
输入包含多组数据对于每组数据，输入一个正整数n（1≤n≤108 ）Output
每组样例输出一行,表示测量的最少次数.Sample Input
110Sample Output
03好像是初中的物理题....最优策略是三分，因为3的余数只有0，1，2；所以当余数为0，分为：m m m 用m与m比较当余数为1，分为： m m m+1 用m与m比较当余数为2，分为： m m+1 m+1 用m+1与m+1比较因为次品是较轻的（已知条件），所以每次比较都可以缩小问题规模到原规模的1/3。（天平的结果相等取第三堆，不相等就直接取轻的那一堆）#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int n; while(scanf("%d",&n) != EOF){ double t = log(n)/log(3); int ans = (int)t; if(t - ans != 0) ans++; cout << ans <<endl; } return 0;}1003:
Problem D The sad match I
Time Limit : 3000/3000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 83 Accepted Submission(s) : 22
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
集训队又要选拔了，今年为了壮大集训队规模，学校打算出很多很多场选拔赛，第i场的持续时间是[ai,bi)。每一场选拔赛都必须至少有一个老队员在现场组织。很遗憾的是，选拔赛可能重叠，比如说可能有一场比赛在[4,9)举行，另一场在[6,10)举行，那么同学们只能选择参加其中一场了。当然，我绝不会关心，你能不能参加的，我关心的是我到底要不要被迫去现场组织比赛。只要两场比赛时间不冲突，他们就可以由同一个老队员组织。现在给出所有的比赛时间，问最少需要多少个老队员作组织工作。例如在[0, 5), [2, 10), [8, 9)各有一场比赛，那么可以让一个老队员去第一、三场，另一个老队员去第二场，这样只需要两个老队员就够了Input
输入的第一行包含一个整数T，表示T个测试样例。每一个测试样例的第一行包含一个正整数n(n≤105 )，表示有n场选拔赛。接下来的n行有每行有2个数，ai和bi, (0≤ai < bi ≤ 105)。Output
对于每组数据，输出至少需要的老队员的人数Sample Input
324 96 1014 941 32 34 96 10Sample Output
212套路题，区间打标记。（虽然数组名是dp，这道题与dp并没有关系....）#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 100;int dp[maxn];int main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); memset(dp,0,sizeof(dp)); while(n--){ int a,b; scanf("%d%d",&a,&b); dp[a]++; dp[b]--; } int Max = 0,sum=0; for(int i=0 ;i<maxn ;i++){ sum += dp[i]; Max = max(sum,Max); } printf("%d/n",Max); } return 0;}1004：Problem F Count the continent
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 49 Accepted Submission(s) : 35
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
给出一个二维矩阵，表示一张地图，0表示海洋,1表示陆地，若一块陆地的坐标为(r,c)，如果另一块陆地为 (r-1,c) 或 (r+1,c) 或 (r,c-1) 或 (r,c+1)，则我们认为这两块陆地相邻，所有相邻的陆地我们称之为一个大陆，求大陆的数量。Input
输入包含多组数据对于每组数据，输入第一行为一个正整数N (N≤10 )，然后给出一个N * N 的矩阵接下来的N行每行N个元素以空格分开，表示该格是陆地还是海洋。Output
对于每组数据，输出大陆的数量。Sample Input
41 1 0 01 1 0 00 0 1 00 0 0 030 1 00 1 00 1 030 0 00 1 00 0 0Sample Output
211dfs入门题：#include <bits/stdc++.h>using namespace std;typedef long long ll;int maze[15][15];int n;int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};bool check(int x,int y){ if(x<=0 || x>n || y<=0 || y>n || !maze[x][y]){ return false; } return true;}void dfs(int x,int y){ maze[x][y] = 0; for(int i=0 ;i<4;i++){ int xx = x + dx[i]; int yy = y + dy[i]; if(check(xx,yy)) dfs(xx,yy); }}int main(){ while(scanf("%d",&n) != EOF){ for(int i=1 ;i<=n ;i++){ for(int j=1 ;j<=n ;j++){ scanf("%d",&maze[i][j]); } } int ans = 0; for(int i=1 ;i<=n ;i++){ for(int j=1 ;j<=n ;j++){ if(maze[i][j]){ ans++; dfs(i,j); } } } printf("%d/n",ans); } return 0;}1005：Problem G Math Problem
Time Limit : 3000/3000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 60 Accepted Submission(s) : 21
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
已知a, n，求，求(Σni=1 an-i(a-1)i-1 ) mod 1000000007Input
输入第一行是一个正整数T(T≤1000)，表示有T组数据；每组数据包含两个正整数a, n(a,n≤109 )。Output
对于每组数据，输出上式的结果。Sample Input
31 12 25 10Sample Output
138717049第一次做这种数学公式变形题，我一开始的思路就是怎么合并式子，但化简时出现了（1/a），然后感觉会带来误差就直接放弃了先做的后面的题。回头做时发现原来时等比数列求和：最后可以化简为： a^n - (a-1)^n然后快速幂即可，但注意负模的处理。#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 1000000007;ll fast_mod(ll x,ll n){ ll ans = 1; while(n>0){ if(n&1) ans = ans * x % mod; x = x * x % mod; n /= 2; } return ans%mod;}int main(){ int T; scanf("%d",&T); while(T--){ ll a,n; scanf("%lld%lld",&a,&n); if(n==1 || a==1){ printf("1/n"); continue; } if(a==0){ printf("0/n"); continue; } ll ans = (fast_mod(a,n) - fast_mod(a-1,n) + mod)%mod; printf("%lld/n",ans); } return 0;}1006Problem I Zeros
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 54 Accepted Submission(s) : 36
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
给出n，计算n！末尾0的个数Input
输入包含多组数据每组数据包含一个正整数n (n≤109 )Output
对于每组数据，输出n！末尾0的个数Sample Input
351001024Sample Output
0124253之前做过的题，印象很深刻.....#include <bits/stdc++.h>using namespace std;typedef long long ll;int ans;void solve(int x){ while(x>=5){ x /= 5; ans += x; }}int main(){ int n; while(scanf("%d",&n) != EOF){ ans = 0; solve(n); cout << ans << endl; } return 0;}1007：Problem J It didn't hate
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 42 Accepted Submission(s) : 29
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
东东特别讨厌“11”，他将所有含有“11”子串的01串（只有0和1组成串）称为光棍。长度为2的光棍有1种：11；长度为3的光棍有3种：011,110,111；长度为4的光棍有8种：0011,0110,1100,1011,1101,1110,0111,1111；给出n，东东想知道长度为n的光棍有多少？Input
输入包含大量数据，大约1000组左右每组数据包含一个1个正整数n(n≤106 )。Output
对于每组数据，输出长度为n的光棍串的数量模1000000007的结果。Sample Input
1469504Sample Output
08632157493DP:设dp[n][0]:长度为n的合法数dp[n][1]:长度为n，首位为1的非法数dp[n][2]:长度为n，首位为0的非法数 所以状态转移方程：dp[n][0] = dp[n-1][0]*2 + dp[n-1][1];dp[n][1] = dp[n-1][2];dp[n][2] = dp[n-1][1] + dp[n-1][2];#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 1000000007;const int maxn = 1e6 + 10;ll dp[maxn][3]; void init(void){ dp[0][0] = dp[0][1] = dp[0][2] = 0; dp[1][0] = 0; dp[1][1] = dp[1][2] = 1; for(int i=2 ;i<maxn ;i++){ dp[i][0] = (dp[i-1][0] * 2 + dp[i-1][1])%mod; dp[i][1] = dp[i-1][2] % mod; dp[i][2] = (dp[i-1][1] + dp[i-1][2]) % mod; } }int main(){ init(); int n; while(scanf("%d",&n) != EOF){ printf("%lld/n",dp[n][0]); } return 0;}1008:Problem C Flip
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 58 Accepted Submission(s) : 24
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
康哥哥和康妹妹经常在一起玩游戏。其中一种就是硬币翻转。游戏的规则如下：1. N*M（N行，M列）的棋盘上，棋盘上每个位置都有个硬币，不是朝上就是朝下；2. 两人轮流进行操作，不能进行操作的人输，当棋盘上所有硬币都朝下时游戏结束；3. 每次操作都在棋盘上选择一个矩形，这个矩形的左上角和右下角位置分别是（x1，y1）和（N，M），然后翻转这个矩形区域内的所有硬币，即把朝上的变成朝下的，把朝下的变成朝上的，（x1，y1）是操作者选定的，唯一限制是每次选定的左上角位置（x1，y1）必须从向上翻转为向下；康哥哥曾经给康妹妹一个问题，假如给你最初棋盘的分布情况，你能确定最终谁能赢吗？假如两人都采用最优策略去玩游戏，游戏每次都是康哥哥先移动。你能帮康妹妹解决这个问题吗？Input
第一行输入一个正整数T，接下来有T组数据(T≤50)。每组数据的首行输入N和M（N，M如上所述），接下来输入N行，每行有M个正整数，每个正整数不是0就是1，0表示硬币向下，1表示硬币向上。（1≤N,M≤20）Output
对于每组数据，如果康哥哥能赢，输出YES，否则输出NO。康哥哥友情提示：这题真的不难，注意观察条件。Sample Input
22 21 11 13 30 0 00 0 00 0 0Sample Output
YESNO博弈。首先明确一点：翻硬币时无论玩家怎么选择矩形左上角的点，点（n,m）都一定会被翻过来。然后简单模拟一下：假设点（n,m）的硬币初始态为0首先哥哥操作： 0 -> 1然后妹妹操作： 1 -> 0哥哥： 0 -> 1妹妹： 1 -> 0哥哥： 0 -> 1妹妹： 1 -> 0.....我们发现，每次妹妹操作完，轮到哥哥翻硬币时，点（n,m）硬币的状态都与初始态相同。而我们又知道结束状态点（n,m）硬币状态一定是0。所以对于上面的例子，哥哥一定是输，因为每次哥哥操作都是在把点（n,m）的硬币从0 -> 1，所以永远到达不了必败点，即棋面全为0的状态哥哥是永远到达不了的。所以：我们只需要判断点（n,m）的初始态是0还是1，如果是1，则哥哥必赢，否则，妹妹必赢。代码：#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int T; scanf("%d",&T); while(T--){ int x,n,m; int ans = 0; scanf("%d%d",&n,&m); for(int i=1 ;i<=n ;i++){ for(int j=1 ;j<=m ;j++){ scanf("%d",&x); } } if(x) puts("YES"); else puts("NO"); } return 0;}
新闻热点
疑难解答
