2017 Chinese Multi-University Training, BeihangU Contest-白红宇

2017 Chinese Multi-University Training, BeihangU Contest

阅读量：5337 次

发布时间：2019-06-15

本文共 8282 字，大约阅读时间需要 27 分钟。

思路：log10(2^m) = m*log10(2)

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb emplace_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define puu pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//head int n, cs = 0;int main() { while(~scanf("%d", &n)) { printf("Case #%d: %d\n", ++cs, (int)(n*log10(2.0))); } return 0;}

View Code

思路：大数比较大小

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define pb push_back#define fi first#define se second#define debug(x) cerr<<#x << " := " << x << endl;#define bug cerr<<"-----------------------"<
            
              pii;typedef pair
             
               pll; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; /**********showtime************/ const int maxn = 1e5+9; char str[maxn]; string ss[maxn]; vector
              
               vec[30]; int a[30][maxn], mx[30]; int id[30], vis[30]; bool cmp(int &x, int &y) { if(mx[x] < mx[y]) return true; else if(mx[x] > mx[y]) return false; else { for (int i = mx[x]-1; i >= 0; --i) { if(a[x][i] > a[y][i]) return false; else if(a[x][i] < a[y][i]) return true; } } return false; }int main(){ int n, cas = 0; while(~scanf("%d", &n)) { for(int i=0; i<26; i++) vec[i].clear(), vis[i] = 0, mx[i] = 0; for(int i=0; i<26; i++) for(int j=0; j
               
                 0) { mx[i] = j+1; } } } for(int i=0; i<26; i++) id[i] = i; sort(id, id+26, cmp); int pos = 0; while(vis[id[pos]]) pos++; int pt = id[pos]; for(int i=pos; i>=0; i--) id[i] = id[i-1]; id[0] = pt; ll ans = 0; for(int i=0; i<26; i++) { ll base = 1; for(int j=0; j

View Code

思路：容斥，考虑对于每种颜色删去后，分成的块中的点两两之间对于这种颜色没有贡献

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdd pair
           
            #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 2e5 + 5;vector
            
              g[N], stk[N];int n, u, v, c[N], sz[N], blo[N], top[N];bool vis[N];void dfs(int u, int o) { sz[u] = 1; for (int v : g[u]) { if(v != o) { dfs(v, u); sz[u] += sz[v]; } } blo[u] = sz[u];}void DFS(int u, int o) { if(stk[c[u]].empty()) top[c[u]] -= sz[u]; else blo[stk[c[u]].back()] -= sz[u]; for (int v : g[u]){ if(v != o) { stk[c[u]].pb(v); DFS(v, u); stk[c[u]].pop_back(); } }}int cs = 0;int main() { while(~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) scanf("%d", &c[i]), vis[c[i]] = true; for (int i = 1; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u); dfs(1, 0); int cc = 0; for (int i = 1; i <= n; ++i) if(vis[i]) top[i] = n, ++cc; else top[i] = 0; DFS(1, 0); LL ans = n*1LL*(n-1)/2*cc; for (int i = 2; i <= n; ++i) ans -= blo[i]*1LL*(blo[i]-1)/2; for (int i = 1; i <= n; ++i) ans -= top[i]*1LL*(top[i]-1)/2; printf("Case #%d: %lld\n", ++cs, ans); for (int i = 1; i <= n; ++i) g[i].clear(), vis[i] = false; } return 0;}

View Code

思路：a的某个长度为x环可以和b中长度为x因子的环构成函数

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdd pair
           
            #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//head const int N = 1e5 + 5;const int MOD = 1e9 + 7;int n, m, a[N], b[N], ca[N], cb[N];LL ans[N];bool vis[N], vv[N];LL q_pow(LL n, LL k) { LL res = 1; while(k) { if(k&1) res = (res * n) % MOD; n = (n * n) % MOD; k >>= 1; } return res;}int main() { int cs = 0; while(~scanf("%d %d", &n, &m)) { for (int i = 0; i < n; ++i) vis[i] = false, ca[i+1] = 0, ans[i+1] = 0; for (int i = 0; i < m; ++i) vv[i] = false, cb[i+1] = 0; for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < m; ++i) scanf("%d", &b[i]); for (int i = 0; i < n; ++i) { if(!vis[i]) { int now = i, cc = 0; while(!vis[now]) { vis[now] = true; now = a[now]; ++cc; } ca[cc]++; } } for (int i = 0; i < m; ++i) { if(!vv[i]) { int now = i, cc = 0; while(!vv[now]) { vv[now] = true; now = b[now]; ++cc; } cb[cc] ++; } } LL res = 1; for (int i = 1; i <= m; ++i) { cb[i] = (cb[i]*1LL*i)%MOD; for (int j = i; j <= n; j += i) { ans[j] = (ans[j] + cb[i]) % MOD; } } for (int j = 1; j <= n; ++j) { if(ca[j]) { res = (res * q_pow(ans[j], ca[j])) % MOD; } } printf("Case #%d: %lld\n", ++cs, res); } return 0;}

View Code

思路：nth_element

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdd pair
           
            #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//head const int N = 1e7 + 5;unsigned x, A, y, B, z, C;int n, m, b[105], id[105];unsigned a[N], ans[N];inline unsigned rng61() { unsigned t; x = x ^ (x << 16); x = x ^ (x >> 5); x = x ^ (x << 1); t = x; x = y; y = z; z = (t ^ x) ^ y; return z;}int cs = 0;int main() { while(~scanf("%d %d %u %u %u", &n, &m, &A, &B, &C)) { for (int i = 1; i <= m; ++i) scanf("%d", &b[i]); x = A, y = B, z = C; for (int i = 1; i <= n; ++i) a[i] = rng61(); printf("Case #%d: ", ++cs); for (int i = 1; i <= m; ++i) id[i] = i; sort(id+1, id+1+m, [](int x, int y){ return b[x] < b[y]; }); nth_element(a+1, a+b[id[m]]+1, a+n+1); ans[id[m]] = a[b[id[m]]+1]; for (int i = m-1; i >= 1; --i) { nth_element(a+1, a+b[id[i]]+1, a+b[id[i+1]]+1); ans[id[i]] = a[b[id[i]]+1]; } for (int i = 1; i <= m; ++i) printf("%u%c", ans[i], " \n"[i==m]); } return 0;}

View Code

思路：打表找规律

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb emplace_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define puu pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//head LL n, k;int main() { int cs = 0; while(~scanf("%lld %lld", &n, &k)) { LL res; if(n == 2) res = k%2 == 0? 2 : 1; else if(k <= n-1) res = k; else { if(k%(n-1) == 1) { --k; if((k/(n-1))%2) res = n; else res = n-1; } else { res = k%(n-1); if(res == 0) res = n-1; --res; } } printf("Case #%d: %lld\n", ++cs, res); } return 0;}