2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest
题号 | A | B | C | D | E | F | G | H | I | J | K |
状态 | Ο | Ο | Ο | . | Ø | Ø | Ø | . | Ο | . | . |
Ο:当场
Ø:已补
. : 待补
简单dp
Thinking&Code:kk
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) #define fpn() freopen("simple.in","r",stdin) #define rd read() using namespace std; typedef long long ll; const int maxn=110; ll dp[maxn][2],l,k; int main(){ while(cin>>l>>k) { clr(dp,0); dp[0][0]=1; for(int i=1;i<=l;i++) { dp[i][0]+=dp[i-1][1]; dp[i][1]+=dp[i-1][0]; if(i-k>=0){ dp[i][1]+=dp[i-k][0]; } } ll ans=0; for(int i=1;i<=l;i++) { ans+=dp[i][1]; } printf("%lld ",ans); } }
B Parallel Lines
Thinking:pai爷
Code:zz
搜索
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) #define fpn() freopen("simple.in","r",stdin) #define rd read() using namespace std; typedef long long ll; const int maxn=110; int m; struct node{ int x,y; }z[110]; pair<int,int>pa; map<pair<int,int>, int>mp; int ans,n; bool vis[110]; inline int gcd(int n,int m) { int r; if(n < m) { r = n; n = m; m = r; } while(n % m) { r = n % m; n = m; m = r; } return m; } inline void dfs(int cnt,int num) { if(cnt == n / 2) { ans = max(ans,num); return; } int i,j; for(i=1;i<=n;i++) if(vis[i]==0) {vis[i]=1;break;} for(j = i + 1;j <= n;j++) { if(vis[j]) { continue; } vis[j] = true; int r,a,b; if(z[i].x == z[j].x) { a = 400001; b = 400002; } else if(z[i].y == z[j].y) { a = 0; b = 0; } else { r = gcd(abs(z[i].x - z[j].x),abs(z[i].y - z[j].y)); if((z[i].x - z[j].x) / r < 0) { r = -r; } a = (z[i].x - z[j].x) / r; b = (z[i].y - z[j].y) / r; } pa.first = a; pa.second = b; int sum = mp[pa] + num; ans = max(ans,sum); mp[pa]++; dfs(cnt + 1,sum); pa.first = a; pa.second = b; mp[pa]--; vis[j] = false; } vis[i] = false; } inline void init(void) { memset(vis,false,sizeof(vis)); mp.clear(); ans = 0; } int main(){ int i,j; while(~scanf("%d",&n)) { init(); for(i = 1;i <= n;i++) { scanf("%d %d",&z[i].x,&z[i].y); } dfs(0,0); printf("%d ",ans); } }