dp？
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 LL f[55][3]; 5 6 int main(){ 7 int N; 8 scanf("%d", &N); 9 f[1][0] = f[1][2] = 1; 10 for(int i = 1; i < N; ++i){ 11 f[i+1][0] = f[i][0] + f[i][1]; 12 f[i+1][1] = f[i][2]; 13 f[i+1][2] = f[i][0] + f[i][1]; 14 } 15 printf("%lld ", f[N][0] + f[N][1]); 16 return 0; 17 }
dp？
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL mod = 1e9 + 7; 5 LL f[105][1000005]; 6 7 int main(){ 8 int N, M, x; 9 scanf("%d %d", &N, &M); 10 for(int i = 0; i <= 100001; ++i) f[0][i] = 1; 11 for(int i = 1; i <= N; ++i){ 12 for(int j = 1; j <= M; ++j) { 13 scanf("%d", &x), x++; 14 f[i][x] = (f[i][x] + f[i-1][x-1]) % mod; 15 } 16 for(int j = 1; j <= 100001; ++j) f[i][j] = (f[i][j] + f[i][j-1]) % mod; 17 } 18 printf("%lld ", f[N][100001]); 19 return 0; 20 }
bfs？
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef pair<int, int> pii; 4 typedef pair<pii, int> piii; 5 const int INF = 1e9; 6 int G[1111][1111], f[1111][1111][2]; 7 int dx[] = {-1, 0, 1, 0}; 8 int dy[] = {0, 1, 0, -1}; 9 char s[1111]; 10 queue<piii> q; 11 12 int main(){ 13 int N; 14 scanf("%d", &N); 15 for(int i = 1; i <= N; ++i){ 16 scanf("%s", s + 1); 17 for(int j = 1; j <= N; ++j) G[i][j] = s[j] == '#' ? 1 : 0, f[i][j][0] = f[i][j][1] = INF; 18 } 19 if(G[1][1]) q.push(piii(pii(1, 1), 1)), f[1][1][1] = 0; 20 else q.push(piii(pii(1, 1), 0)), f[1][1][0] = 0; 21 while(!q.empty()){ 22 piii now = q.front(); q.pop(); 23 int nx = now.first.first, ny = now.first.second, o = now.second; 24 for(int i = 0; i < 4; ++i){ 25 int xx = nx + dx[i], yy = ny + dy[i]; 26 if(xx < 1 || xx > N || yy < 1 || yy > N) continue; 27 if(G[xx][yy] && o) continue; 28 int oo = o || G[xx][yy]; 29 if(f[xx][yy][oo] != INF) continue; 30 f[xx][yy][oo] = f[nx][ny][o] + 1; 31 q.push(piii(pii(xx, yy), oo)); 32 } 33 } 34 int ans = min(f[N][N][0], f[N][N][1]); 35 printf("%d ", ans == INF ? -1 : ans); 36 return 0; 37 }
……无语了
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 1e5 + 10; 5 LL W[maxn], V[maxn], b[66]; 6 int id[maxn]; 7 8 bool cmp(int i, int j){ 9 return W[i] > W[j]; 10 } 11 12 // Template 13 //清除前缀0，如果结果是空字符串则设为0 14 inline void clear(string& a){ 15 while(a.length()>0 && a[0]=='0') 16 a.erase(0, 1); 17 if(a == "") 18 a = "0"; 19 } 20 21 //如果a>=b则返回真（如果包含前缀零会被消除） 22 bool isBigger(string a, string b){ 23 clear(a); 24 clear(b); 25 if(a.length() > b.length()) 26 return true; 27 if(a.length()==b.length() && a>=b) 28 return true; 29 return false; 30 } 31 32 33 //两个高精度正整数加法 a+b 34 string Add(string a, string b){ 35 //1、对位，将两个数补零直到其具有相同长度 36 while(a.length() < b.length()) 37 a = '0' + a; 38 while(a.length() > b.length()) 39 b = '0' + b; 40 //2、补零，在开头再加一个0以便进位 41 a = '0' + a; 42 b = '0' + b; 43 //3、从低位开始相加，注意进位 44 for(int i=a.length()-1; i>=0; i--){ 45 a[i] = a[i] + b[i] - '0'; 46 if(a[i] > '9'){ 47 a[i] = a[i] - 10; 48 a[i-1] += 1; 49 } 50 } 51 clear(a); 52 return a; 53 } 54 55 //两个高精度正整数减法 a-b 56 string Minus(string a, string b){ 57 bool aBigger = true; 58 //1、对位，将两个数补零直到其具有相同长度 59 while(a.length() < b.length()) 60 a = '0' + a; 61 while(a.length() > b.length()) 62 b = '0' + b; 63 //2、推测结果正负值，调整为前大后小 64 if(a < b) 65 { 66 aBigger = false; 67 string buf = b; 68 b = a; 69 a = buf; 70 } 71 //3、从低位开始相减，注意借位 72 for(int i=a.length()-1; i>=0; i--){ 73 if(a[i] >= b[i]){ 74 a[i] = a[i] - (b[i] - '0'); 75 }else{ 76 a[i] = a[i] + 10; 77 a[i-1] -= 1; 78 a[i] = a[i] - (b[i] - '0'); 79 } 80 } 81 clear(a); 82 if(!aBigger) 83 a = '-' + a; 84 return a; 85 } 86 87 template<typename T> string to(const T& t){ 88 ostringstream oss; //创建一个格式化输出流 89 oss<<t; //把值传递如流中 90 return oss.str(); 91 } 92 93 int main(){ 94 int N, M; 95 scanf("%d %d", &N, &M); 96 string sum("0"), ans("0"); 97 for(int i = 1; i <= N; ++i) scanf("%lld", W + i), sum = Add(sum, to(W[i])), id[i] = i; 98 sort(id + 1, id + 1 + N, cmp); 99 for(int i = 1; i <= M; ++i){ 100 int u, v; 101 LL w; 102 scanf("%d %d %lld", &u, &v, &w); 103 V[u] ^= w, V[v] ^= w; 104 } 105 for(int i = 1; i <= N; ++i){ 106 int x = id[i]; 107 for(int j = 0; j <= 60; ++j) { 108 if(V[x] & (1LL << j)){ 109 if(b[j]) V[x] ^= b[j]; 110 else {b[j] = V[x], ans = Add(ans, to(W[x])); break;} 111 } 112 } 113 } 114 cout << Minus(Add(ans, ans), sum) << endl; 115 return 0; 116 }
学习了py
1 N, M = list(map(int, raw_input().strip().split())) 2 W = list(map(int, raw_input().strip().split())) 3 sum = sum(W) 4 id = sorted([(W[i], i) for i in range(N)], reverse=True) 5 V = [0 for i in range(N)] 6 for i in range(M): 7 u, v, w = list(map(int, raw_input().strip().split())) 8 V[u-1] ^= w 9 V[v-1] ^= w 10 b = [0 for i in range(61)] 11 ans = 0 12 for i in range(N): 13 x = id[i][1] 14 for j in range(61): 15 if V[x] & (1 << j): 16 if b[j]: 17 V[x] ^= b[j] 18 else: 19 b[j] = V[x] 20 ans += W[x] 21 break 22 print(ans + ans - sum)