[CCPC2016]网赛部分比赛代码

来自HDOJ：

5833 ( Zhu and 772002 )

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 using namespace std;
 35 #define fr first
 36 #define sc second
 37 #define cl clear
 38 #define BUG puts("here!!!")
 39 #define W(a) while(a--)
 40 #define pb(a) push_back(a)
 41 #define Rint(a) scanf("%d", &a)
 42 #define Rll(a) scanf("%I64d", &a)
 43 #define Rs(a) scanf("%s", a)
 44 #define Cin(a) cin >> a
 45 #define FRead() freopen("in", "r", stdin)
 46 #define FWrite() freopen("out", "w", stdout)
 47 #define Rep(i, len) for(int i = 0; i < (len); i++)
 48 #define For(i, a, len) for(int i = (a); i < (len); i++)
 49 #define Cls(a) memset((a), 0, sizeof(a))
 50 #define Clr(a, x) memset((a), (x), sizeof(a))
 51 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))
 52 #define lrt rt << 1
 53 #define rrt rt << 1 | 1
 54 #define pi 3.14159265359
 55 #define RT return
 56 #define lowbit(x) x & (-x)
 57 #define onenum(x) __builtin_popcount(x)
 58 typedef long long LL;
 59 typedef long double LD;
 60 typedef unsigned long long ULL;
 61 typedef pair<int, int> pii;
 62 typedef pair<string, int> psi;
 63 typedef pair<LL, LL> pll;
 64 typedef map<string, int> msi;
 65 typedef vector<int> vi;
 66 typedef vector<LL> vl;
 67 typedef vector<vl> vvl;
 68 typedef vector<bool> vb;
 69 
 70 const int maxn = 333;
 71 const int maxm = 2020;
 72 const LL mod = 1000000007;
 73 typedef struct Bucket {
 74     LL b[maxm];
 75 }Bucket;
 76 int n;
 77 LL a[maxn];
 78 bool _p[maxm];
 79 LL prime[maxm];
 80 int pcnt;
 81 LL dp[maxn][maxn];
 82 
 83 void init() {
 84     Cls(_p); pcnt = 0;
 85     For(i, 2, maxm) {
 86         if(_p[i] == 0) {
 87             prime[pcnt++] = i;
 88             for(int j = i * 2; j < maxm; j+=i) {
 89                 _p[j] = 1;
 90             }
 91         }
 92     }
 93 }
 94 
 95 void gao(int i, LL x) {
 96     for(int j = 0; j < pcnt; j++) {
 97         if(x % prime[j]) continue;
 98         int cnt = 0;
 99         while(x % prime[j] == 0) {
100             x /= prime[j];
101             cnt ^= 1;
102         }
103         dp[i][j] = cnt;
104     }
105 }
106 
107 LL quickmul(LL x, LL n, LL mod) {
108     LL ret = 1;
109     while(n) {
110         if(n & 1) ret = (ret * x) % mod;
111         x = (x * x) % mod;
112         n >>= 1;
113     }
114     return ret;
115 }
116 
117 int main() {
118 //    FRead();
119     int T, _ = 1;
120     Rint(T);
121     init();
122     W(T) {
123         Cls(dp);
124         printf("Case #%d:
", _++);
125         Rint(n);
126         For(i, 1, n+1) {
127             cin >> a[i];
128             gao(i, a[i]);
129         }
130         int p = 0;
131         Rep(i, pcnt) {
132             For(j, p, pcnt) {
133                 if(dp[j][i]) {
134                     For(k, i, pcnt) {
135                         swap(dp[j][k], dp[p][k]);
136                     }
137                     break;
138                 }
139             }
140             if(!dp[p][i]) continue;
141             For(j, p+1, pcnt) {
142                 if(dp[j][i]) {
143                     For(k, i, pcnt) {
144                         dp[j][k] ^= dp[p][k];
145                     }
146                 }
147             }
148             p++;
149         }
150         cout << (quickmul(2,n-p,mod)-1+mod)%mod << endl;
151     }
152     RT 0;
153 }

5835 ( Danganronpa )

 1 #include <vector>
 2 #include <list>
 3 #include <map>
 4 #include <set>
 5 #include <deque>
 6 #include <queue>
 7 #include <stack>
 8 #include <bitset>
 9 #include <algorithm>
10 #include <functional>
11 #include <numeric>
12 #include <utility>
13 #include <complex>
14 #include <sstream>
15 #include <iostream>
16 #include <iomanip>
17 #include <cstdio>
18 #include <cmath>
19 #include <cstdlib>
20 #include <cstring>
21 #include <ctime>
22 #include <cassert>
23 using namespace std;
24 int s[11];
25 int main(){
26     int T,n;
27     int sum,ans,coco;
28     scanf("%d",&T);
29     int pp = 1;
30     while(T--){
31         int maxn = 0;
32         sum = 0;
33         scanf("%d",&n);
34         for(int i=0;i<n;i++){
35             scanf("%d",&s[i]);
36             sum +=s[i];
37             maxn = maxn < s[i] ? s[i] : maxn;
38         }
39         ans = sum/2;
40         if(maxn > sum/2){
41            coco = (sum - maxn) * 2 + 1;
42            ans = coco > ans ? ans : coco;
43         }
44         printf("Case #%d: %d
",pp++,ans);
45     }
46 }

5832 ( A water problem )

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 using namespace std;
 35 #define fr first
 36 #define sc second
 37 #define cl clear
 38 #define BUG puts("here!!!")
 39 #define W(a) while(a--)
 40 #define pb(a) push_back(a)
 41 #define Rint(a) scanf("%d", &a)
 42 #define Rll(a) scanf("%I64d", &a)
 43 #define Rs(a) scanf("%s", a)
 44 #define Cin(a) cin >> a
 45 #define FRead() freopen("in", "r", stdin)
 46 #define FWrite() freopen("out", "w", stdout)
 47 #define Rep(i, len) for(int i = 0; i < (len); i++)
 48 #define For(i, a, len) for(int i = (a); i < (len); i++)
 49 #define Cls(a) memset((a), 0, sizeof(a))
 50 #define Clr(a, x) memset((a), (x), sizeof(a))
 51 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))
 52 #define lrt rt << 1
 53 #define rrt rt << 1 | 1
 54 #define pi 3.14159265359
 55 #define RT return
 56 #define lowbit(x) x & (-x)
 57 #define onenum(x) __builtin_popcount(x)
 58 typedef long long LL;
 59 typedef long double LD;
 60 typedef unsigned long long ULL;
 61 typedef pair<int, int> pii;
 62 typedef pair<string, int> psi;
 63 typedef pair<LL, LL> pll;
 64 typedef map<string, int> msi;
 65 typedef vector<int> vi;
 66 typedef vector<LL> vl;
 67 typedef vector<vl> vvl;
 68 typedef vector<bool> vb;
 69 
 70 const int maxn = 10000100;
 71 char str[maxn];
 72 int len;
 73 int mod(int num) {
 74     int ret = 0;
 75     Rep(i, len) {
 76         ret = (int)(((LL)ret * 10 + (str[i] - '0')) % num);
 77     }
 78     return ret;
 79 }
 80 
 81 int main() {
 82 //    FRead();
 83     int _ = 1;
 84     while(Rs(str)!=EOF) {
 85         printf("Case #%d: ", _++);
 86         len = strlen(str);
 87         int num = 0;
 88         if(len <= 10) {
 89             Rep(i, len) {
 90                 num *= 10;
 91                 num += str[i] - '0';
 92             }
 93             if(num == 0 || num % 10001 == 0) {
 94                 puts("YES");
 95                 continue;
 96             }
 97             if(num != 0 || num % 10001 != 0) {
 98                 puts("NO");
 99                 continue;
100             }
101         }
102         int t = mod(10001);
103         if(t == 0) puts("YES");
104         else puts("NO");
105     }
106     RT 0;
107 }

5842 ( Lweb and String )

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 using namespace std;
 35 #define fr first
 36 #define sc second
 37 #define cl clear
 38 #define BUG puts("here!!!")
 39 #define W(a) while(a--)
 40 #define pb(a) push_back(a)
 41 #define Rint(a) scanf("%d", &a)
 42 #define Rll(a) scanf("%I64d", &a)
 43 #define Rs(a) scanf("%s", a)
 44 #define Cin(a) cin >> a
 45 #define FRead() freopen("in", "r", stdin)
 46 #define FWrite() freopen("out", "w", stdout)
 47 #define Rep(i, len) for(int i = 0; i < (len); i++)
 48 #define For(i, a, len) for(int i = (a); i < (len); i++)
 49 #define Cls(a) memset((a), 0, sizeof(a))
 50 #define Clr(a, x) memset((a), (x), sizeof(a))
 51 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))
 52 #define lrt rt << 1
 53 #define rrt rt << 1 | 1
 54 #define pi 3.14159265359
 55 #define RT return
 56 #define lowbit(x) x & (-x)
 57 #define onenum(x) __builtin_popcount(x)
 58 typedef long long LL;
 59 typedef long double LD;
 60 typedef unsigned long long ULL;
 61 typedef pair<int, int> pii;
 62 typedef pair<string, int> psi;
 63 typedef pair<LL, LL> pll;
 64 typedef map<string, int> msi;
 65 typedef vector<int> vi;
 66 typedef vector<LL> vl;
 67 typedef vector<vl> vvl;
 68 typedef vector<bool> vb;
 69 
 70 const int maxn = 100100;
 71 char str[maxn];
 72 int ascii[257];
 73 int a[maxn];
 74 int n, q;
 75 int ord;
 76 int dp[maxn];
 77 int s[maxn];
 78 
 79 int bs(int ll, int rr, int v) {
 80     while(ll <= rr) {
 81         int mm = (ll + rr) >> 1;
 82         if(s[mm] < v) ll = mm + 1;
 83         else rr = mm - 1;
 84     }
 85     return ll;
 86 }
 87 
 88 int main() {
 89 //    FRead();
 90     int T, _ = 1;
 91     Rint(T);
 92     W(T) {
 93         ord = 1; q = 1;
 94         Rs(str);
 95         memset(ascii, -1, sizeof(ascii));
 96         memset(dp, 0, sizeof(dp));
 97         memset(s, 0x7f7f7f7f, sizeof(s));
 98         printf("Case #%d: ", _++);
 99         n = strlen(str);
100         Rep(i, n) {
101             if(ascii[str[i]] == -1) {
102                 ascii[str[i]] = ord;
103                 a[q++] = ord++;
104             }
105             else {
106                 a[q++] = ascii[str[i]];
107             }
108         }
109         int ans = 0;
110         For(i, 1, n+1) {
111             dp[i] = bs(1, i, a[i]);
112             s[dp[i]] = min(s[dp[i]], a[i]);
113             ans = max(ans, dp[i]);
114         }
115         printf("%d
", ans);
116     }
117     RT 0;
118 }