关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年7月17日
论数学的重要性 — Studyingfather Dalao 的欢乐赛题解

比赛链接:[https://www.luogu.org/contestnew/show/8609]

0x-1


首先十分感谢 StudyingFater 大佬出的这场比赛让我们感受到这场数学的魅力(大雾

不过这个抄袭省选题目真的就有点….

0x00 奇怪的支付方式


题目链接:[https://www.luogu.org/problemnew/show/T36519]

题目一看,仿佛回到了小学题目的噩梦,然而作为一位正经Oier,尝试法可不是我们应该做的,仔细一看,发现这个操作似乎有点面熟,我们来把问题抽象一下

有一个整数\(n\)最少有几个数,确保中间任意两个数相加后得到值的集合为[1,n]

是不是有点眼熟?没错,这就在 初学DP(4) – 多重背包及其优化 – Codevs 3269 中的二进制优化法

     1
  10
100

看看上面这一串的数字是不是选择任意两个数加起来都可以得到(100)2以内的任何数?

由此可得,这道题目的答案就是n的二进制位数+1

当然快速求位数也很简单–\(log_2(n)\)

程序:

#include <cstdio>
#include <cmath>
using namespace std;

int n;

int main(){
    scanf("%d",&n);
    printf("%d",(int)log2(n)+1);
}

惊不惊喜?意不意外?

0x01 我爱打飞盘


题目链接:[https://www.luogu.org/problemnew/show/T36562]

首先,作为一名乌市一中Oier,打飞盘是一项必备技能

读题!!!看到余数这个东西,第一个想到的就是同余定理

其次,对于数据范围搜索显然是会TLE的,我们就要另辟蹊径了

综合以上两个条件,很容易想到DP的思想,首先定义函数\(f(i,j)\)

其中\(i\)表示第\(i\)个数字,\(j\)表示以这个数字为结尾的数列余数为\(j\)有几种情况

很容易得到下面的代码:

#include <cstdio>
#include <cstring>
using namespace std;

int n,f,g,h,a[2100];
int dp[2100][2100];
int cnt;

inline int max(int a,int b) {return a>b?a:b;}

int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);dp[i][a[i]%f]++;}// 自己的情况先加上
    for(int i=1;i<=n;i++){ 
        g=a[i]%f;// 当前数对于f的余数   
        for(int j=1;j<i;j++){// 遍历以前的情况
            for(int k=0;k<f;k++){// 遍历余数的情况
                h=(g+k)%f;  // 当前的余数
                dp[i][h]+=dp[j][k];// 累加
            }
        }
    }
    for(int i=1;i<=n;i++) cnt+=dp[i][0];// 统计余数为0的情况
    printf("%d",cnt);// 输出
}

但是时间复杂度呢?\(O(n^2f)\)显然这个数据范围承受起来有点费劲,我们要想办法优化

观察代码发现,我们每次都是就之前的状况累加,也就是说我们没有必要对之前的情况进行遍历,只需要记住累加和就行了,但是余数这个东西比较麻烦的在于,你如何确保不被累加运算?

滚动数组解决一切

不过是不是忘记了什么???

取模啊!!!

所以正确的代码如下:

#include <cstdio>
#include <cstring>
using namespace std;

int n,f,g,h,l,a[2100],m=1e8;
int dp[2100],dp2[2100];
int cnt;

int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){ 
        g=a[i]%f; 
        for(int k=0;k<f;k++){
            h=(g+k)%f;     
            dp[h]+=dp2[k];
            dp[h]%=m;
        }
        for(int k=0;k<f;k++) {dp2[k]+=dp[k];dp2[k]%=m;dp[k]=0;}
        dp2[g]++;// 做到自己在把自己加上防止累加
    }
    printf("%d",dp2[0]);
}

0x02 硬币游戏


题目链接: [https://www.luogu.org/problemnew/show/T36547]

如果不是因为我有事情走的早的话我这题也能A

这题一眼看过去?博弈论?算了怎么高端的东西不好推,我们想想别的

显然,无论怎么操作,最后的结果一定是(int)n/m个m与n%m这样几堆硬币

所以我们计算总共可能的移动次数,对2取模即可得到结果

代码如下:

#include <cstdio>
#include <cmath>
using namespace std;

int T,n,m;
int temp,temp2;

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        temp=n/m*(m-1);// 正确的操作应该是temp=n/m*m; temp-=m;合并了一下
        temp2=n%m;
        if(temp2>0) temp2--;// 有可能n%m==0
        if((temp2+temp)%2==0) printf("1\n");
        else printf("0\n");
    }
}

INFxINF END


textsms