一场挺傻逼的比赛。。。。被一群省队学弟吊起来打。250/735
惨哦。
1002 Build a tree 【待补】
暴力建图题，好像坑点较多。
1005 Euler theorem
简单签到
#include <bits/stdc++.h> using namespace std; int T; int main() { scanf("%d",&T); while (T--) { int a; cin>>a; cout<<(a-1)/2+2<<endl; } return 0; }
1006 Free from square 【补】
据说和NOI题很像，后来看了看题解，分组背包+状压
#include <bits/stdc++.h> const int mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using namespace std; int prim[600],vis[600]; long long val[555]; int temp[10] = {2,3,5,7,11,13,17,19}; int dp[2][555][555]; int cnt = 0; int N,K,now; void init(){ for (int i = 2; i<=500;i++){ if (vis[i])continue; if (i>19) prim[++cnt] = i; for (int j = i+i;j <= 500; j+=i) vis[j] = 1; } } long long getval(int t){ long long ans = 1; for (int i = 0; i<8;i++){ if (t%2) ans*=temp[i]; t/=2; } return ans; } int main() { int T; cin >> T; init(); //cout << getval((1<<8)-1) ; for (int i = 0;i<(1<<8) ; i++) val[i] = getval(i); while (T--) { cin >> N >> K; memset(dp,0,sizeof(dp)); now = 1; dp[1][0][0] = 1; for (int i = 1; i<=cnt && prim[i]<=N ;i++){ //枚举组 now = !now; for (int k = 0;k<(1<<8);k++) for (int t = 0;t<=K;t++) dp[now][t][k] = dp[!now][t][k]; //转移不选择的状态 for (int k = 0 ; k <(1<<8);k++){ //枚举小质数状态 if (val[k]*prim[i] > (long long)N ) continue; for (int j = 0 ; j < (1<<8) ; j++){ //枚举转移状态 if ((j&k)!=0) continue; for (int t = 1;t <= K; t++){ //枚举数字个数 dp[now][t][(j|k)] = (dp[now][t][(j|k)] + dp[!now][t-1][j]) % mod; } } } } for (int k = 1; k<(1<<8);k++){ if (val[k] > (long long)N) continue; for (int j = 0;j<(1<<8);j++){ if ((j&k)!=0) continue; for (int t = 1;t<=K;t++) dp[now][t][j|k] = (dp[now][t][j|k] + dp[now][t-1][j]) % mod; } } int ans = 0; for (int i = 1;i<=K;i++){ for (int j = 0 ;j<(1<<8) ; j++){ if (i<K) dp[now][i][j] = (dp[now][i][j] * 2) % mod; //是否有1 ans = (ans + dp[now][i][j]) % mod; } } cout <<ans+1<<endl; // 单独一个1 } return 0; }
1008 Hard challenge
极角排序，然后两指针check扫一遍，竟然1A了。
#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using namespace std; struct node { long long x,y; int val; double c; int p; }P[50034]; int N; long long sum[100034]; bool pd(int a,int b) { if (b>N)b-=N; return ((P[a].x*P[b].y - P[a].y * P[b].x) > 0); } bool cmp(node a,node b) { if (a.p == b.p ) { if (a.p == 1) { return a.c > b.c; } else return a.c < b.c; } return a.p > b.p; } int main() { int T; //freopen ("in.txt","r",stdin); scanf("%d",&T); while (T--) { scanf("%d",&N); memset(sum,0,sizeof(sum)); for (int i = 1; i<=N; i++) { scanf("%I64d%I64d%d",&P[i].x,&P[i].y,&P[i].val); if (P[i].y >=0 ) P[i].p = 1; else P[i].p = 0; if (P[i].y == 0 && P[i].x < 0) P[i].p = 0; P[i].c = P[i].x / sqrt( ((1.0*P[i].x)*(1.0*P[i].x)) + ((1.0*P[i].y)*(1.0*P[i].y))); } if (N==1) { puts("0"); continue; } sort(P+1,P+N+1,cmp); for (int i = 1; i<=N;i++) sum[i] = sum[i-1] + P[i].val; for (int j = 1; j<=N; j++) sum[N+j] = sum[N+j-1] + P[j].val; int r; for (r = 1; r<=N && P[r].p >=1;r++); int l = 1; long long ans = 0; r--; for (int i = 1; i<=N; i++) { while (pd(i,r)) r++; if (i==r||i+N==r) r++; ans = max((sum[r-1] - sum[i-1])*(sum[N] - (sum[r-1] - sum[i-1])),ans); } printf("%I64d ",ans); } return 0; }
1010 Just do it
智商可能也许大概我也不愿意承认，就是被碾压了。
分析了一下原因 可能是因为思路不够开阔，还有就是学弟呼呼过，影响了心态。
#include <cstdio> const int N = 200000; int a[N]; int main() { int T; scanf("%d", &T); while (T --) { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++ i) { scanf("%d", a + i); } for (int k = 0; 1 << k <= m; ++ k) { if (m >> k & 1) { for (int i = 1 << k; i < n; ++ i) { a[i] ^= a[i - (1 << k)]; } } } for (int i = 0; i < n; ++ i) { printf("%d%c", a[i], " "[i == n - 1]); } } }
1011 Kolakoski
直接递推。
#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using namespace std; int a[21234567]; void init() { int cnt1 = 1; int cnt2 = 1; while (cnt1 <= 10000000) { a[++cnt1] = (a[cnt1-1]==1?2:1); if (a[cnt2+1] == 2) a[++cnt1] = a[cnt1-1]; cnt2++; } } int main() { int N; a[1] =1; init(); cin >> N; while (N--) { int i; cin >> i; cout << a[i]<<endl; } return 0; }