等差数列分组
本题其实针对的是连续的序列,那么我们可以认为是针对子段的事情,可以利用GCD来搞点事情!只要Gcd两个数的差,不是1,我们就可以认为还在一个数列里面
for(int i=2;i<=n;i++) { cin>>a[i]; int x=abs(a[i]-a[i-1]); if(t==0) { t=x; continue; } int y=__gcd(x,t); if(y==1) { ans++; t=0; continue; } t=y; }
01字符串
利用递归的思想,如果我们知道第N行第K个字符,是由第N-1行的哪一个字符替换来的,同时是替换后的第几个,我们就可以知道当前字符是什么,所以问题转为了第N-1行的问题,并且K的规模变为了一半。
因此只要递归执行即可。(尾部递归,时间复杂度log(N))
#include <bits/stdc++.h> using namespace std; bool query(int n, int k) { if (n == 1) return true; bool v = query(n - 1, (k - 1) / 2 + 1); return (k % 2) == v; } int main() { int n, k; while(cin>>n>>k){ cout << (query(n, k) ? "1" : "0") << endl; } return 0; }
最大奇数约数
对于n以内的所有偶数 2,4,6,8.....,其最大奇约数和除以2后的 1,2,3,4.....是一样的,所以递归为原题数据规模的一半。
对于n以内的所有奇数1,2,3,4..... ,则其最大奇约数就是其本身,所以加起来的话就是(n+1/2)^2。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007; ll cal(ll n) { if(n < 1) return 0; ll k = (n + 1) / 2 % MOD; return (k * k + cal(n / 2)) % MOD; } int main() { ios::sync_with_stdio(false); ll t, n; cin >> t; while (t--) { cin >> n; cout << cal(n) << endl; } return 0; }
最大化摸鱼
考虑f[i]表示i~n之间的最大空闲时间。
那么可以发现:
当前时间点i空闲: f[i] = f[i+1]+1
当前时间点i不空闲: 那么考虑当前时间点的多种选项,每个选项代表一个f[i+a[j]] {j属于当前所有选项},从中找一个最大的就行,即:f[i] = max(f[i+a[j]])
然后到这来就行了。
#include<cstdio> #include<algorithm> #define maxn 10039 using namespace std; int N, K, f[maxn]; struct FLY{ int t, w; }a[maxn]; int cmp(FLY a, FLY b){return a.t<b.t;} int main(){ freopen("1.in", "r", stdin); scanf("%d%d", &N, &K); for(int i = 1; i < K+1; i++)scanf("%d%d", &a[i].t, &a[i].w); sort(a+1, a+1+K, cmp); int tmp = N; for(int i = K; i > 0; i--){ for(int j = tmp; j > a[i].t; j--) f[j] = f[j+1]+1; while(a[i].t==a[i-1].t){ f[a[i].t] = max(f[a[i].t], f[a[i].t+a[i].w]); i--; } f[a[i].t] = max(f[a[i].t], f[a[i].t+a[i].w]); tmp = a[i].t-1; } for(int j = tmp; j > 0; j--)f[j] = f[j+1]+1; printf("%d", f[1]); return 0; }
5的次数
简单的数位DP
int len, num[N], dp[N][N][2][2], tar = 5; int dfs(int pos, int sum, int lead, int limit){ if(pos == 0) return sum; if(~dp[pos][sum][lead][limit]) return dp[pos][sum][lead][limit]; int up = limit ? num[pos] : 9; int ans = 0; for(int i = 0; i <= up; ++ i){ ans += dfs(pos - 1, sum + (i == tar), lead && i == 0, limit && i == up); } return dp[pos][sum][lead][limit] = ans; } int solve(int x){ len = 0; while(x){ num[++ len] = x % 10; x /= 10; } memset(dp, -1, sizeof(dp)); return dfs(len, 0, 1, 1); }
日历游戏
有t组数据,每次给定一个日期,两个人轮流对这个日期进行操作:天数+1或月份+1。先到达2006.11.4者赢。
方法一:记忆化搜索 + 简单博弈论
提示是个好东西:
说明/提示 建议先把所有情况都算出来^_^
因此,我们可以用记搜来求出所有的情况——
#include <iostream> #include <cstdio> using namespace std; int t,x,y,z,f[2007][15][35],m[13]={0,31,29,31,30,31,30,31,31,30,31,30,31}; //,m数组存储每个月有多少天 bool vis[2007][15][35]; bool check(int year,int month,int day){//判断是否超过目标日期 if(year<2006) return true; if(year==2006 && month<11) return true; if(year==2006 && month==11 && day<4) return true; return false; } int dfs(int year,int month,int day){ if((year%4!=0 || year==1900) && month==2 && day==29) return 1; if(day>m[month])//若天数超过当前月的,则说明到了下一个月 month++,day=1;//月份++,从1号重新开始 if(month>12)//若已经超过了12个月,说明到了下一年 year++,month=1;//年份++,从1月重新开始 //说句闲话:相当于进位(?) if(vis[year][month][day])//如果已经查找过直接返回结果即可 return f[year][month][day]; vis[year][month][day]=1;//标记为已查找 if(day<=m[month+1] && check(year,month+1,day))//注意,这里有个小细节:如果要改变月份,应先判断一下当前天数是否下一个月的天数(因为每个月的天数不一样) f[year][month][day]=((dfs(year,month+1,day))^1);//^1相当于取反,若是为1则返回0,若是为0则返回1 if(check(year,month,day+1)) f[year][month][day]|=((dfs(year,month,day+1)^1)); return f[year][month][day]; } int main(){ f[2006][11][3]=1; dfs(1900,1,1);//从1900年1月1日开始搜索 scanf("%d",&t); while(t--){ scanf("%d%d%d",&x,&y,&z); if(f[x][y][z]) printf("YES\n"); else printf("NO\n"); } return 0; }
方法二:DP + 逆推
#include <iostream> #include <cstdio> using namespace std; int t,x,y,z,f[2007][13][32],m[13]={0,31,29,31,30,31,30,31,31,30,31,30,31}; void dp(){ int year=2006,month=11,day=4;//从目标日期开始逆推 f[2006][11][4]=1;//注意,这里要赋值为1,不然会玄学WA(别问我咋知道的 while(!(year==1900 && month==1 && day==1)){ int y1=year,m1=month,d1=day; day--; if(day==0){//说明这一个月已经推完了 month--;//继续倒着推上一个月 if(month==0)//若是这一年都推完了 month=12,year--;//(同理) day=m[month]; if(((year%4==0 && year%100!=0) || year%400==0) && month==2) day++;//若是闰年的二月份,天数++ } if(f[y1][m1][d1]==1){//如果当前这个日期不满足 f[year][month][day]=2;//则说明上一个(因为是逆推)日期满足 continue; //因为是这两个人轮流进行操作 } y1=year;m1=month+1;d1=day; if(m1==13)//(进位~) y1++,m1=1; if(f[y1][m1][d1]==1)//同上 f[year][month][day]=2; else f[year][month][day]=1; } } int main(){ dp(); scanf("%d",&t); while(t--){ scanf("%d%d%d",&x,&y,&z); if(f[x][y][z]==2) printf("YES\n"); else printf("NO\n"); } return 0; }
方法三:规律
首先不看年份,每次操作必定会使日期和月份的和的奇偶性发生变化。目标日期11.4(11+4=15)是奇数。而天数或月份+1都会导致其和的奇偶性发生改变。
但是要注意两个特殊的日期 :9月30日(日+1为10.1,月+1为10.30)和11月30日(日+1为12.1,月+1为12.30),奇偶性可能是保持不变的,但是因为Adam足够聪明(),所以可以通过加月份来避开这一天,因此若是日期一开始是偶数或者是这两天,先者赢,否则后者赢。
#include <iostream> #include <cstdio> using namespace std; int t,x,y,z; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d%d",&x,&y,&z); if((y==9 && z==30) || (y==11 && z==30) || (y+z)%2==0) printf("YES\n"); else printf("NO\n"); } return 0; }