Codeforces Round #383 _python作死系列

A. Arpa’s hard exam and Mehrdad’s naive cheat

题意求1378的n次方的最后一位，懒的写循环节瞎快速幂

py3 int和LL 合并为int了

 def q_(x):

     a = 8

     ans = 1

     while(x>0):

         if(x&1):

             ans = ans*a%10

         a = a*a%10

         x = x//2

     print(ans%10)

 c =int(input())

 q_(c)

B. Arpa’s obvious problem and Mehrdad’s terrible solution

ZZ题读题浪费了很长时间

C. Arpa's loud Owf and Mehrdad's evil plan

找环不合法的情况肯定是度为单数的点然后 DFS就ok 偶数/2 求lcm

 def gcd(x,y):

     return x if y==0 else gcd(y,x%y)

 def lcm(x,y):

     return x//gcd(x,y)*y

 def dfs(x,y):

     if(vis[x]):

         return y

     vis[x] = 1

     return dfs(c[x-1],y+1)

 n =int(input())

 c = []

 for x in input().split():

     c.append(int(x))

 vis = [0]*(n+1)

 ind = [0]*(n+1)

 for i in range(n):

     ind[i+1]+=1

     ind[c[i]]+=1

 mk = 1

 for i in range(n):

     if(ind[i+1]&1):

         mk = 0

 ans = 1

 if(mk):

     for i in range(n):

         if(vis[i+1]==0):

             val = dfs(i+1,0)

         if(val%2==0):

             val//=2

         ans = lcm(ans,val)

     print(ans)

 else:

     print("-1");

D. Arpa's weak amphitheater and Mehrdad's valuable Hoses

约妹纸，要么约集合，要么约集合中的一个（可用list优化）并查集加01背包

但是问题来了...这个题做了整整五个小时没A................... TLE到死 python的多重循环比C++慢百倍....怪不得DE这种题一般没python的出现....

优化了range 继续TLE 直到现在我放弃了

虽然红了两页但是学到了不少....蛮阿Q的...

n, m, w = map(int, input().split())

W = []

B = []

W = list(map(int, input().split()))

B = list(map(int, input().split()))

par = [0]*(n+10)

for i in range(0, n):

    par[i] = i

def find(x):

    if(x == par[x]):

        return x

    else:

        par[x] = find(par[x])

        return par[x]

def unite(x, y):

    x = find(x)

    y = find(y)

    if(x != y):

        par[x] = y

for i in range(m):

    x, y = map(int, input().split())

    unite(x-1, y-1)

dp = [0]*(w+10)

q = [0]*(n+10)

for i in range(n):

    if(i==find(i)):

        cnt = 0

        V = 0

        E = 0

        for k in range(n):

            if(find(k)==find(i)):

                q[cnt] = k

                cnt += 1

                V += W[k]

                E += B[k]

        for j in range(w,-1,-1):

            if(j>=V):

                dp[j] = max(dp[j],dp[j-V]+E)

            for k in range(cnt):

                if(j>=W[q[k]]):

                    dp[j] = max(dp[j],dp[j-W[q[k]]]+B[q[k]])

print(dp[w])

理论AC代码

后来去CF上拿了份代码把python翻译成C++ 就AC了

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,w,cnt;

int fa[],a[],b[],f[],q[];

int find(int x)

{

    if(!fa[x]) return x;

    fa[x]=find(fa[x]);

    return fa[x];

}

int main()

{

    int i,r1,r2,j,k;

    scanf("%d%d%d",&n,&m,&w);

    for(i=;i<=n;i++) scanf("%d",&a[i]);

    for(i=;i<=n;i++) scanf("%d",&b[i]);

    for(i=;i<=m;i++)

    {

        scanf("%d%d",&r1,&r2);

        j=find(r1); k=find(r2);

        if(j!=k)fa[k]=j;

    }

    for(i=;i<=n;i++)

        if(fa[i]==)

        {

            cnt=; int ww=,bb=;

            for(j=;j<=n;j++) if(find(j)==i)

            {

                q[++cnt]=j; ww+=a[j]; bb+=b[j];

            }

            for(j=w;j>=;j--)

            {

                //f[i][j]=f[i-1][j];

                for(k=;k<=cnt;k++) if(j>=a[q[k]]) f[j]=max(f[j],f[j-a[q[k]]]+b[q[k]]);

                if(j>=ww) f[j]=max(f[j],f[j-ww]+bb);

            }

        }

    printf("%d",f[w]);

    return ;

}

AC代码

待补
E.

ARPA

Codeforces Round #383 _python作死系列