NOIP2018提高组省一冲奖班模测训练（六）

NOIP2018提高组省一冲奖班模测训练（六）

https://www.51nod.com/Contest/ContestDescription.html#!#contestId=80

20分钟AC掉第一题。

然后第二题感觉和最长公共子序列有关，怒干2h，写出了一个错误的算法

只拿了百分之20的数据的分

第三题觉得是数学题，然后推不出来（然而正解是dp……似曾相识的场景）

A 工程制图基础

https://www.51nod.com/Contest/Problem.html#!#contestProblemId=574&contestJudgeId=0

 

lxl在工程制图基础课上获得了一个数轴。

开始时数轴上是空的，lxl每次可以指定两个数 $\mathrm{a,ta,t 进行操作，将数轴上坐标为 [a],[2a],...,[ta][a],[2a],...,[ta] 的位置变化一次（ [a][a] 表示取 aa 的整数部分），变化是指如果该位置没有点则打一个点，有点则把点擦掉。}$

lxl在做了 $\mathrm{nn 次操作之后发现数轴上只剩下一个点了。他告诉你了他每一次操作的 a,ta,t ，请你求出最后剩下的点的坐标。}$

 

记 $\mathrm{T=\sum tT=\sum t 。}$

对于 $\mathrm{30\%30\% 的数据，满足 T\le 1000T\le 1000 。}$

对于 $\mathrm{80\%80\% 的数据，满足 T\le 200000T\le 200000 。}$

对于 $\mathrm{100\%100\% 的数据，满足 T\le 2000000,n\le 5000,1\le ai<1000,1\le ti\le TT\le 2000000,n\le 5000,1\le ai<1000,1\le ti\le T 。}$

 

输入

第一行一个正整数n。
接下来n行，每行两个数ai,ti，表示第i次操作的参数。其中ai为小数点后有六位的实数，ti为正整数。

输出

一行一个正整数表示剩下的点的坐标。

输入样例

3
1.618034 13
2.618034 7
1.000000 21

输出样例

20

---

看完题目觉得搞一个set不就完事了？？
写完后交上就AC了
这题是考STL吗，这么裸？？？

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

set<int> s;
int n;

int main()
{
    scanf("%d", &n);
    _for(i, 1, n)
    {
        double a; int t;
        scanf("%lf%d", &a, &t);
        _for(i, 1, t)
        {
            int k = a * i;
            if(!s.count(k)) s.insert(k);
            else s.erase(k);
        }
    }
    
    set<int>::iterator it = s.begin();
    printf("%d
", *it);

    return 0;
}

正解非常的骚

用异或

因为同样的数异或两次就为0了

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    _for(i, 1, n)
    {
        double a; int t;
        scanf("%lf%d", &a, &t);
        _for(i, 1, t) ans ^= int(a * i);
    }
    printf("%d
", ans);
    return 0;
}

B 土木工程概论

https://www.51nod.com/Contest/Problem.html#!#contestProblemId=575&contestJudgeId=0

 

土木工程概论课每周会布置一项写paper的作业。

由于lxl并不想写，他会在某度上搜索一篇文章A，然后截取其中的一段并且进行一些操作变成自己的文章B。

你现在拿到了lxl的文章B，也某度到了原文章A。

lxl的每一次操作有修改（把一个字符换成另一个字符）、添加（在某个位置插入一个字符）、删除（删除一个字符）三种操作。

你想知道lxl最少进行了多少次操作。（一开始的截取不计入操作次数）

 

对于 $\mathrm{30\%30\% 的数据， |A|,|B|\le 10|A|,|B|\le 10 。}$

对于 $\mathrm{100\%100\% 的数据， |A|,|B|\le 1000|A|,|B|\le 1000 ，数据组数 \le 10\le 10 ，输入的串中只包含小写字母。}$ 

输入

输入包含多组数据。
对于每组数据，有两行，分别表示A和B的内容。

输出

对于每组数据输出一行一个数表示最少操作次数。

输入样例

aaaaa
aaa
abcabc
bcd
abcdef
klmnopq

输出样例

0
1
7

---

这道题做的非常艰辛
比赛的时候一看到题就想到了字符距离的一道题，和这道题很像，只不过这道题可以截取
当时觉得应该改一下就可以了。然而并没有那么简单
怒刚两小时只过了百分之20的点

然后讲解的时候有个地方没听懂，优化删除操作的那个地方
然后最后干脆自己推一遍，推出了一些与标程有些地方不同的式子（本质应该是一样的），然后交上去，AC了
看不懂题解就还是要靠自己……

这道题显然是dp
dp[i][j]表示第i位和第j位一定匹配的操作次数
答案为min(dp[i][lenb])
注意这里是一定匹配，不是前i个和前j个
为什么要这样？
因为这里其实包含了截取操作
我们必然从字符串A中截一段下来
而答案为min(dp[i][lenb])
也就是说对于一个dp[i][lenb]
字符串A的i之后的字符是没有用到的
因为第i位和B的最后一位匹配了
所以相当于字符串A的i之后的字符删掉了
而操作过程中涉及插入，删除，会把一部分开头的字符删掉
这就实现了从A截取一段下来
也是这题最最关键的一点。
这个状态的设计导致了状态转移方程比字符串距离的那道题复杂了很多

那么转移方程是什么呢
（1）修改
对于dp[i][j]
要第i位和第j位一定匹配
那么显然看第i位是不是等于第j位
不是的话就把第i位改成第j位（注意不能改第j位，第j位是B，我们是修改A变成B）
那么i和j之间的操作次数就是dp[i-1][j-1]
所以dp[i][j] = dp[i-1][j-1] + (a[i] != b[j]))

（2）插入

对于dp[i][j]
要第i位和第j位一定匹配
我们可以在第i位之前插入与第b[j]位相同的字符
也就是在i-1与i的缝隙插入一个，然后i以后（包括i）都往右移
那么第j位已经和插入的这个字符匹配了，而第i位移到右边，接下来是i和第j+1位要匹配，所以是dp[i][j+1]
也就是说dp[i][j] + 1 = dp[i][j+1]
这是刷表法，我习惯填表法
所以就是d[i][j-1] + 1 = dp[i][j]
即dp[i][j] = dp[i][j-1] + 1

（3）删除
删除是最麻烦的
如果要删除的话
就需要把i前面（不包括i）删掉一段到k，使得k与j-1匹配,然后i与j匹配（转移方程中依然要加上(a[i] != b[j])）

也就是说把k + 1, k + 2……i - 2, i - 1删掉
显然这里有i - k - 1个数
也就是说
dp[i][j] = min(dp[i][j], dp[k][j-1] + i - k - 1 + (a[i] != b[j]))
显然我们需要dp[k]][j-1] + i - k - 1 + (a[i] != b[j])这个玩意最小，这样才是最优的
那么显然取决与ｋ，ｊ和ｉ都和当前状态有关
那么如果我们枚举ｋ的话，需要Ｏ（ｎ）
那么总的复杂度就是Ｏ（ｎ^３），会超时
所以这里有个骚操作
用一个数组来记录最优的k，重分利用之前的结果

具体来说

dp[k][j-1] + i - k - 1 + (a[i] != b[j])这个式子
真正会变化的是dp[k][j-1]-k
那么我们就开一个
m[i][j]，表示使dp[k][j]-k最小的k
那么转移的时候我们直接调用

dp[m[i][j-1]][j-1] + i - m[i][j-1] - 1 + (a[i] != b[j])就好了

那么我们考虑怎么维护这个m数组
首先k<i，因为最少就删除0个，让i-1与j-1匹配，i与j匹配
对于dp[k][j]-k
发现与dp值有关
那就每次算出一个dp值就去更新m数组
dp[i][j]-i，可以去更新m[i+1][j]，注意这里是i+1，因为k<i
所以就比较dp[i][j]-i与dp[m[i][j]][j] - m[i][j]去更新m[i+1][j]就好了

终于写完了。

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

const int MAXN = 1e3 + 10;
char a[MAXN], b[MAXN];
int dp[MAXN][MAXN], m[MAXN][MAXN];

int main()
{
    while(~scanf("%s%s", a + 1, b + 1))
    {
        int lena = strlen(a + 1), lenb = strlen(b + 1);
        memset(m, 0, sizeof(m));
        memset(dp, 0x3f, sizeof(dp));
        _for(i, 0, lena) dp[i][0] = 0;
        _for(i, 0, lenb) dp[0][i] = i;
        
        int ans = 1e9;
        _for(i, 1, lena)
        {
            _for(j, 1, lenb)
            {
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i] != b[j]));
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
                dp[i][j] = min(dp[i][j], dp[m[i][j-1]][j-1] + i - m[i][j-1] - 1 + (a[i] != b[j]));
                
                if(dp[i][j] - i < dp[m[i][j]][j] - m[i][j]) m[i + 1][j] = i;
                else m[i + 1][j] = m[i][j];
            }
            ans = min(ans, dp[i][lenb]);
        }
        printf("%d
", ans);
    }
    
    return 0;
}

C 思想道德修养与法律基础

https://www.51nod.com/Contest/Problem.html#!#contestProblemId=576&contestJudgeId=0

lxl抢到了 $\mathrm{TT 次思修课小班讨论的名额。}$

对于第 $\mathrm{ii 次小班讨论，参与人数为 nini，所有人围在一个圆桌旁边坐着。其中有一些人喜欢抬杠，如果有挨着坐的连续超过 kiki 个人都喜欢抬杠，那么他们就会吵起来导致小班讨论无效。}$

lxl不希望自己辛苦抢到的名额因为这些人而作废，他想知道对于每一次小班讨论有多少种不发生吵架的安排座位的方案。（旋转后同构的算一种）

爱抬杠的人是任意个且除了爱抬杠不作其它区分。

对于 $\mathrm{20\%20\% 的数据， t\le 20,n,k\le 20t\le 20,n,k\le 20}$

对于 $\mathrm{100\%100\% 的数据， t\le 50,n,k\le 2000t\le 50,n,k\le 2000}$

 

输入

第一行为T，表示小班讨论的次数。
接下来T行每行两个数n和k。

输出

T行，每行一个数表示合法的方案数对100000007取余的结果。

输入样例

3
3 1
3 3
4 1

输出样例

2
4
3

---

这道题是一道动规题
这种方案数的题目有些是数学解法，有些是动规解法。
正解的思路非常的巧妙
先不考虑循环同构的情况，把所有方案求出来，然后再去掉循环同构的方案

（1）不考虑循环同构的情况下得出所有方案
这个时候只需要满足一个条件，连续抬杠的人<=k人
这个条件有个地方不好处理，就是可能首尾相接超过个人
所以我们先考虑第一个人不是抬杠的人的方案，然后再考虑首尾相接
设f[i][j]表示有i个人，尾部有连续j个人抬杠的方案数
如果j = 0，说明第j个人不是抬杠的，那么之前的状态都可以转移过来
即f[i][0] = sigma(f[i-1][j]) 0 <= j <= k
如果j！=0，说明第j个人是抬杠的，也就是说第j个人的前j-1个人也是抬杠的，那么显然有f[i][j] = f[i-1][j-1]
边界f[1][0] = 1规定第一个人不抬杠
所以规定第一个人不抬杠的方案就可以用f数组求出
那么考虑第一个人抬杠，这个时候就可能出来首尾相接的情况
在这个时候，如果不是全都抬杠的人（更新答案的时候要特判，具体见程序），我们就可以找到至少一个人不抬杠
那么我们开始滚动（或者叫循环？？就那个意思）这个序列，把这个不抬杠的人滚到第一个人的位置
这个时候我们可以发现就可以转化成一开始f数组算的第一个不抬杠的方案
那我们反过来想
那么在f数组中，对于f[i][j],可以把后j个人从后滚到前使得第一个人抬杠，有j种方案。
那么不滚动的话就是原来的f[i][j]
所以一共有f[i][j] * (j + 1)种方案
那么我们设g[i]为长度为i，不考虑循环同构的方案数
则g[i] = sigma(f[i][j] * (j + 1)) 0 <= j <= k
那么第一部分就完成了

（2）考虑怎么去掉循环同构的情况
怎样才会循环同构？？
比如1234，2341， 3412， 4123这4个是循环同构的。
那么我们是不是可以把每个方案除以序列长度？？
不对！
比如1010， 0101。这个序列长度是4，但是只有两种循环同构的情况
因为这个序列含有10这个循环节，使得只需要循环2次就可以变成原来的样子
这怎么办？
我们可以枚举循环节的长度，然后方案数就除以循环节的长度，这样就没有问题
但是，如果循环节套循环节怎么办？
我们就算出长度为i，没有循环节的方案
然后把这个i作为循环节去算，这样就不会有循环节套循环节的情况
所以设h[i]为长度为i，没有循环节的方案
显然要使得没有循环节，那就把有循环节的方案数减去即可
所以h[i] = g[i] - sigma(h[j]) j整除i
注意这里减去的是h[j], 不是g[j]
因为减去的也要保证没有循环节套循环节的情况
比如说10101010，如果是用g数组减去的话，j=2的时候这种情况会减去，j=4的时候又会减去
显然是减了两次，就错了
那么最后统计答案，就枚举循环节的长度，加上该长度下的方案除以长度就好了

最后我写的这份代码最慢的点跑了890ms
标程跑了300ms左右
我这份代码有很大的常数优化空间
比如h数组其实不需要都算出来，因为只有是n的因子才需要h数组，所以可以需要的时候再算
再比如逆元部分可以线性求逆初始化，也可以用一个数组存下来不重复算

但是我为了代码的简洁以及懒，就没有去改了。

#include<bits/stdc++.h>
#define add(a, b) a = (a + b) % mod
#define sub(a, b) a = (a - b + mod) % mod
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

const int mod = 100000007;
const int MAXN = 2e3 + 10;
int f[MAXN][MAXN], g[MAXN], h[MAXN];
int n, k;

int power(int a, int b)
{
    int res = 1 % mod; a %= mod;
    for(; b; b >>= 1)
    {
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
    }
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    
    while(T--)
    {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        memset(h, 0, sizeof(h));
        scanf("%d%d", &n, &k);
        
        f[1][0] = 1;
        _for(i, 2, n)
        {
            _for(j, 0, k) add(f[i][0], f[i-1][j]);
            _for(j, 1, k) f[i][j] = f[i-1][j-1];
        }
        
        _for(i, 1, n)
            _for(j, 0, k)
                add(g[i], 1ll * f[i][j] * (j + 1));
        
        _for(i, 1, n)
        {
            h[i] = g[i];
            REP(j, 1, i)
                if(i % j == 0)
                    sub(h[i], h[j]);
        }

        int ans = k >= n; //全都抬杠 
        _for(i, 1, n)
            if(n % i == 0)
                add(ans, 1ll * h[i] * power(i, mod - 2));
        
        printf("%d
", ans);
    }
    
    return 0;
}