等差数列分组
本题其实针对的是连续的序列，那么我们可以认为是针对子段的事情，可以利用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;
}