开始: 2023-05-10 00:00:00

230510稠州PK赛

结束: 2023-05-12 12:55:00
当前  2025-01-24 16:45:29  类型: IOI  状态: 已经结束 

等差数列分组

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