总结：
~~A、B、C不是白给题吗~~，D题dp，需要一些思维，E题拓扑排序(+dfs+字典树)，还是要转个弯
~~cf的题都要转个弯~~

A. K-divisible Sum

题目大意:构造一个长度为n的数组,每个数是正整数,要求整个数组的和是k的倍数,并且整个数组最大的数最小.输出数组的最大值。

思路：

首先数组的和越小越好，同时数组的和肯定要比 $n$ 大， $sum=(n+k-1)/k*k$ 算出数组最小的和，最后再平均分配，如果有多则部分数组加一

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int main() {
    int t=read();
    while(t--) {
        int n=read(),k=read();
        if(k<n) k=(n+k-1)/k*k;
        printf("%d\n",k/n+(k%n!=0));
    }
}

B. Inflation

题目大意:给定一个数组 $p$ ,记 $s_i$ 为前 $i$ 项的前缀和,定义一个通货膨胀率 $c_i=p_i/s_i−1∗100\%$ .数组 $p$ 从0开始计数,要求每个 $i≥1$ 的位置的通货膨胀率 $c_i$ 都不超过一个上界 $k\%$ .当你处在i这个位置并且通货膨胀率超标的时候,可以增大前面 $[0,i−1]$ 中的某些值使得通货膨胀率不超标.求最少需要增加的总和是多少,能使每个位置都不引发蛋疼率超标.

思路：

居然从 $B$ 题开始就出问题了，一开始我的想法很简单，找到最大通货膨胀率，然后通过增加 $p_0$ 使得这个通货膨胀率不超标，但是这是除法！增加的值对分数的贡献是和与分母的大小有关的，而与分数的大小无关，分母大的，分数减小的效果相较而言小些，分母大的，分数减小的效果相较而言大些。
正解显而易见，不就是暴力去模拟吗！！
同样的复杂度，为什么要去找最大通货膨胀率，然后想加一次就完事，一个一个的减不会慢又不会错。

所以，模拟能过的，就去模拟！

Mycode:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll a,sum,ans,tmp;
int main() {
    int t=read();
    while(t--) {
        ll n=read(),k=read();
        sum=read();
        ans=0;
        for(int i=2;i<=n;++i) {
            a=read();
            if(a*100>k*sum) {
                tmp=ceil((double)100/k*a-sum);
                sum+=tmp;
                ans+=tmp;
            }
            sum=sum+a;
        }
        cout<<ans<<endl;
    }
}
/*
1
5 3
3 2 2 2 4
125
*/

C. Longest Simple Cycle

题目大意:有 $n$ 个链,每个链长度为 $c_i$ 即带有 $c_i$ 个节点.链的标号从0开始,从标号为1的链开始,每个链都带有两个值 $a_i$ 和 $b_i$ 表示当前第 $i$ 个链的第一个点会连向上一个点第 $a_i$ 个点,最后一个点会连向上一个链的第 $b_i$ 个点.求形成的整个图上,长度最长的简单环的长度.

思路：

刚看到这题，大佬们都说找最大环，然后我也去求最大环了，就去找连通的环，然后取最大的了，这是错的，内部形成的环可能比整个连通的环大，这是极有可能会误解的(看到的例子也具有误导性)。所以还是要模拟，不断更新最大的环，但不一定要是整个连通的环，可以是它内部的环。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
typedef long long int ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll a[maxn],b[maxn],c[maxn];
int main() {
    int t=read();
    while(t--) {
        int n=read();
        for(int i=1; i<=n; ++i) c[i]=read();
        for(int i=1; i<=n; ++i) a[i]=read();
        for(int i=1; i<=n; ++i) {
            b[i]=read();
            if(a[i]>b[i]) swap(a[i],b[i]);
        }
        ll tmp=b[2]-a[2]+1,ans=tmp+c[2];
        for(int i=3; i<=n; ++i) {
            if(a[i]==b[i])
                tmp=1;
            else
                tmp+=a[i]-b[i]+c[i-1]+1;
            tmp=max(tmp,b[i]-a[i]+1);
            ans=max(ans,tmp+c[i]);
        }
        cout<<ans<<endl;
    }
}
/*
1
4
3 1 9 4 
-1 1 1 9 
-1 1 1 1
*/

D. Journey

题目大意:有 $n+1$ 个城市,标号从0开始,用一个字符串表示每个城市的链接情况,如果第i位为L表示有一条有向边从 $i$ 连向 $i−1$ 反之对应.在这张图上,每从一个节点走到另外一个节点上,就会导致整个图上的所有边的方向反转一次.求从所有的点出发,能走到多少个点的个数.

思路：

想到了就很简单的dp题，但需要转弯。从点 $i$ 出发，如果能到达 $i+1$ ，那么 $sum_i=2$ ，如果能到达 $i+2$ ，那么 $sum_i=2+sum_{i+2}$ ， $sum_i$ 表示从 $i$ 点出发往右能参观多少个城市。很明显， $i$ 到 $i+2$ 后相当于走了两次，整个图还是原图，那么此时就相当于从点 $i+2$ 出发。从 $i$ 点出发往左能参观多少个城市的求法同上，知道往左和往右能参观多少个城市后，求能访问多少个就是两者相加 $-1$ 了。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+7;
typedef long long int ll;
int dp[maxn],pd[maxn];
int main() {
    ios_base::sync_with_stdio(false);
       cin.tie(0);
       string s;
       int t,n;
    cin>>t;
    while(t--) {
        cin>>n>>s;
        s=" "+s;
        memset(dp,0,sizeof dp);
        memset(pd,0,sizeof pd);
        n+=1;
        dp[1]=dp[2]=1;
        if(n>1&&s[1]=='L') dp[2]+=1;
        for(int i=3;i<=n;++i) {
            if(s[i-1]=='R') {
                dp[i]=1;
                continue;
            }
            dp[i]=2;
            if(s[i-2]=='R') dp[i]+=dp[i-2];
        }
        pd[n-1]=pd[n]=1;
        if(n>1&&s[n-1]=='R') pd[n-1]+=1;
        for(int i=n-2;i;--i) {
            if(s[i]=='L') {
                pd[i]=1;
                continue;
            }
            pd[i]=2;
            if(s[i+1]=='L') pd[i]+=pd[i+2];
        }
        for(int i=1;i<=n;++i) cout<<dp[i]+pd[i]-1<<' ';
        cout<<'\n';
    }
}

E. Pattern Matching

题目大意:有 $n$ 个模式串 $p$ 以及 $m$ 个字符串 $s$ .模式串只包含通配符和小写字符.对于每个字符串 $s$ 有一个下标 $mt$ ,现在要求重排所有模式串的顺序,并开始从前往后尝试每个字符串 $s$ 的匹配,如果s与模式串中按顺序的第一个匹配成功,那么检查这个匹配到的模式串在本来的顺序中的位置是否和字符串指定的下标 $mt$ 相同,如果不相同则失败,如果所有的字符串都能匹配上并且下标对应,就认为这个排列是正确的,输出一种正确的 $p$ 的排列或者报告无解.

思路：

最简单的情况就是字符串 $s$ 与模式串在本来的顺序中下标为 $mt$ 的模式串不同，那么直接输出"NO"。

其次考虑这个题的顺序安排方式：如果一个模式串 $p_i$ 匹配到字符串 $s_j$ 那么在 $mt_j\ !=\ i$ 的时候，那么正确的顺序中 $p_i$ 一定要出现在 $p_{mt_j}$ 后面， $p_{mt_j}$ 连一条有向边指向 $p_i$ ， $p_i$ 的入度加一，那么这就恰好是一个求拓扑排序的问题了，如果存在拓扑排序，输出"YES"并输出这个顺序，否则输出"NO"。

一个不太容易处理的地方是怎么找到所有与字符串 $s_j$ 匹配的模式串。一种简单粗暴的方法是用二进制枚举所有可能与字符串 $s_j$ 匹配的串，然后通过 $map$ 来判断是否有这个串，光是枚举所有可能的串，复杂度就要 $O(k*2^k)$ ，这里 $k$ 很小，这样写没问题(代码)。另外一种方法是按照模式匹配的套路，把每个模式串插到字典树中，然后用类似数位dp的办法搜索与字符串 $s_j$ 匹配的模式串，效率很高。

接着是拓扑排序的内容了，简单的 $bfs$ 处理就行了，然后开个数组记录顺序，如果得到的是 $n$ 个模式串的顺序，那么说明这个序列是正确的，反之说明有环出现，无解。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxV=4e5+7,maxE=2e6+7;
int n,m,k;
char s[10];
int val[maxV],ch[maxV][30],sz;
int head[maxn],to[maxE],Next[maxE],du[maxn],tot;
vector<int>vec;
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    ++du[y];//入度 
}
void insert(int x) {
    int u=0;
    for(int i=1,c;i<=k;++i) {
        c=islower(s[i])?s[i]-'a'+1:27;
        if(!ch[u][c]) ch[u][c]=++sz;
        u=ch[u][c];
    }
    val[u]=x;
}
inline void dfs(int u,int len) {
    if(len==k+1) {
        if(val[u]) vec.push_back(val[u]);
        return;
    }
    if(ch[u][s[len]-'a'+1]) dfs(ch[u][s[len]-'a'+1],len+1l);
    if(ch[u][27]) dfs(ch[u][27],len+1);
}
inline void bfs() {
    queue<int>que;
    vec.clear();
    for(int i=1;i<=n;++i) if(!du[i]) que.push(i);
    int u,v;
    while(que.size()) {
        u=que.front();
        que.pop();
        vec.push_back(u);
        for(int i=head[u];i;i=Next[i]) {
            v=to[i];
            du[v]-=1;
            if(!du[v]) que.push(v);
        }
    }
    if(vec.size()==n) {
        puts("YES");
        for(int pos:vec)
            printf("%d ",pos);
    }
    else puts("NO");
}
int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i) {
        scanf("%s",s+1);
        insert(i);
    }
    for(int i=1,x;i<=m;++i) {
        scanf("%s%d",s+1,&x);
        vec.clear();
        dfs(0,1);
        bool flag=true;
        for(auto pos:vec) {
            if(pos!=x) add(x,pos);
            else flag=false;
        }
        if(flag) return puts("NO"),0;
    }
    bfs();
    return 0;
}

Educational Codeforces Round 103 (Rated for Div. 2)

A. K-divisible Sum

思路：

B. Inflation

思路：

C. Longest Simple Cycle

思路：

D. Journey

思路：

E. Pattern Matching

思路：