文章目录

Codeforces Round #542

A Toy Train

题意： 有一个n个节点的环，编号1,n,在每个节点有若干个糖果，需要运送到某个节点，我们现在从节点1出发，每次只能从一个节点中取出一个糖果，但可以放下多个，现在问将所有的糖果放到目的地需要多久？
分析: 我们选择先遍历一遍，假设从第i个节点出发，那么将第i个节点的所有糖果送到目的地最短需要多久，我们发现如果有 a 个糖果，至少需要a-1圈，剩下将最后一个糖果送到目的地即可，所以我们留下的一定是最近的。这样预处理所有的时间，再判断将所有的都送回去哪个节点里面是最慢的即可

int n,m;
LL dis(int a,int b){
    // assert(a!=b);
    if(b >= a) return b-a;
    return n+b-a;
}
const int maxn =5e3+10;
LL a[maxn],b[maxn],c[maxn];
LL ans[maxn];
vector<int> G[maxn];
int main(void)
{
    cin>>n>>m;
    LL u,v;
    rep(i,0,m){
        scanf("%lld %lld",&u,&v);
        G[u].Pb(v);
    }

    // cout<<endl;
    rep(i,1,n+1){
        if(G[i].empty())continue;
        LL Max = INF;
        for(auto c: G[i]) Max = min(Max,dis(i,c));
        LL l = G[i].size();
        c[i] = (l-1)*n+Max;
        // cout<<i<<" "<<c[i]<<" "<<Max<<endl;
    }
    rep(i,1,n+1){
        rep(j,1,n+1)
           {
            if(c[j] != 0)
            ans[i]= max(ans[i],dis(i,j)+c[j]);
           }
        printf("%lld%c",ans[i]," \n"[i==n] );
    }
    

   return 0;
}

B. Wrong Answer

题意: 理解题目给出的程序，构造出数组使得正确答案和题目给出程序输出结果相差k
分析: k为1e9 ，n = 2000， k/n = 5*10^5,正好满足要求，所以直接构造争取答案是取n个，下面给出一种构造方法：
前1998个置0,1999个为负假设为 a，2000个为正b
那么b就是程序的输出
b + k = (a+b)*2000
需要b+k 整除2000，我们可以从1e6往下找，找到第一个能整除的即可

const int maxn = 1e5+10;
LL a[maxn];
int main(void)
{
  LL k;
  cin>>k;
  LL v= 1e6-1;
  while((k+v)%2000!= 0) v--;
  LL t = (v+k)/2000;
  LL m = v-t;
  for(int i = 1;i <= 2000-2;++i)
    a[i] = 0;
  a[1999] = -m;
  a[2000] = v;
  LL tt = 0;
  cout<<2000<<endl;
  for(int i = 1;i <= 2000;++i)
    printf("%lld%c",a[i]," \n"[i==2000]),tt += a[i];

   return 0;
}

C Morse Code

题意： 给出一段莫尔斯密码，求密码的子串翻译成的不同原文有多少个？现在不停的向密码之后添加0和1，每次添加都要输出答案
分析：trie树+dp，用trite树记录莫尔斯序列，trie树上的节点的值是如果由此向上到根节点组成的莫尔斯密码子串翻译成的不同原文的个数，每一次都添加从后往前加入到tire树种，如果出现之前从未出现的子串，就以这个节点开始往后枚举 26个莫尔斯密码，假设当前节点为u，从这之后是0111为合法的密码 ，之后的节点在tire树上的位置是v dp[u] = dp[u] + dp[v];




const int maxn = 3000+3,maxm = maxn*(maxn+1)/2;
int a[maxn];
int ch[maxm][2],dp[maxm],fa[maxm];
int sz;
LL ans;
int main(void)
{
    int n;
    cin>>n;
    dp[0] = 1;
    fa[0] = -1;
    sz = 1;
    rep(i,0,n){
        scanf("%d",&a[i]);
        int u = 0;
        for(int j = i;j >= 0;u = ch[u][a[j--]]){
            if(ch[u][a[j]]) continue;
            int v = u;
            int b = 0;
            for(int k = 0;k < 4 && v != -1;++k){
                b = b<<1|a[j+k];
                if(k < 3||(b!=3&&b!=5&&b!=14&&b!=15))
                    dp[sz] = (dp[sz]+dp[v])%mod;
                v = fa[v];
            }
            ans = (ans+dp[sz])%mod;
            fa[sz] = u;
            ch[u][a[j]] = sz++;
        }

        printf("%lld\n",ans);
    }
    

   return 0;
}