Codeforces Round #383 _python作死系列

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

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

py3 int和LL 合并为int了

 1 def q_(x):
 2     a = 8
 3     ans = 1
 4     while(x>0):
 5         if(x&1):
 6             ans = ans*a%10
 7         a = a*a%10
 8         x = x//2
 9     print(ans%10)
10 
11 c =int(input())
12 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

 1 def gcd(x,y):
 2     return x if y==0 else gcd(y,x%y)
 3 def lcm(x,y):
 4     return x//gcd(x,y)*y
 5 def dfs(x,y):
 6     if(vis[x]):
 7         return y
 8     vis[x] = 1
 9     return dfs(c[x-1],y+1)
10 n =int(input())
11 c = []
12 for x in input().split():
13     c.append(int(x))
14 vis = [0]*(n+1)
15 ind = [0]*(n+1)
16 for i in range(n):
17     ind[i+1]+=1
18     ind[c[i]]+=1
19 mk = 1
20 for i in range(n):
21     if(ind[i+1]&1):
22         mk = 0
23 ans = 1
24 if(mk):
25     for i in range(n):
26         if(vis[i+1]==0):
27             val = dfs(i+1,0)
28         if(val%2==0):
29             val//=2
30         ans = lcm(ans,val)
31     print(ans)
32 else:
33     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 xelse: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 = 0V = 0E = 0for k in range(n):if(find(k)==find(i)):q[cnt] = kcnt += 1V += 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])

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

#include
#include
using namespace std;
int n,m,w,cnt;
int fa[1100],a[1100],b[1100],f[1100],q[1100];
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=1;i<=n;i++) scanf("%d",&a[i]);for(i=1;i<=n;i++) scanf("%d",&b[i]);for(i=1;i<=m;i++){scanf("%d%d",&r1,&r2);j=find(r1); k=find(r2);if(j!=k)fa[k]=j;}for(i=1;i<=n;i++) if(fa[i]==0){cnt=0; int ww=0,bb=0;for(j=1;j<=n;j++) if(find(j)==i) {q[++cnt]=j; ww+=a[j]; bb+=b[j];}for(j=w;j>=0;j--) {//f[i][j]=f[i-1][j];for(k=1;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 0;
}

待补
E.

F.

转载于:https://www.cnblogs.com/Geek-xiyang/p/6145092.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！