| 题号 | 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); } }
Thinking：pai爷 kk
Code ：pai爷
#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=100010; int n,a[maxn],ans[maxn],t; void init() { scanf("%d%d",&n,&t); for(int i=1;i<=n;i++) scanf("%d",&a[i]); } void work() { int q=a[1]; ll sum=a[1]; ans[1]=t/a[1]+1; for(int i=2;i<=n;i++) { sum+=a[i]; if(a[i]>q) q=a[i]; //printf("%d %d ",sum,q); if(t>=sum) ans[i]=(t-sum)/q+2; else ans[i]=1; } for(int i=1;i<=n;i++) printf("%d ",ans[i]); } int main() { init(); work(); }
补题：kk
假设原图的最短路径是$dis$，首先，求出1到v的距离$dis1[v]$和u到2的距离$dis2[u]$（建立正向图和反向图，两边dijkstra求出），那么对于一条边$(u,v,w)$，如果你把它反转之后使得路径更短了，那么必然是$dis1[v]+w+dis2[u]<dis$，只有这样才会优化。
否则，如果$(u,v,w)$这条边是最短路的必经路径的话，那么最短路必定变长。
现在我们考虑怎么判断一条路是最短路的必经路径。网上有所谓的tarjan求有向图的桥的模板，个人认为这是错误的，首先有向图没有桥的概念，其次那个板子，我同一组数据，把边的输入顺序换一下，得到的桥是不一样的。那么怎么做呢？
如果现在我们把这幅图除了最短路上的其他边全部都去掉，得到一幅“最短路图”，如果我们把这个看成一个无向图的话，那么这个无向图的桥是不是就是最短路的必经边？
所以现在我们把问题分解成了：1，建立最短路图，这个就判断$dis1[u]+w+dis2[v]==dis$就可以了，2，tarjan求无向图的桥。
但这道题有一个坑点，就是题目说了会有重边，而tarjan解决重边是会有问题的，所以即便某条边在最短路图上是桥，我们还是必须得判断下这条边是否唯一，这个就用map来做。
吐槽：网上的std一大半都是错的，能ac，但是我随便造个有重边的样例就能hack它，区域赛的后台数据也这么水吗？
#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; const int maxn=100010; typedef long long ll; int dfn[maxn],low[maxn],tim; struct edge{ int from,to,id; ll w; }a[maxn]; int n,m,tot,cnt,h1[maxn],h2[maxn]; int ans[maxn]; bool vis[maxn]; ll dis1[maxn],dis2[maxn]; map<pair<pair<int,int >, ll>,int >mp; void init(){ clr(h1,-1),clr(h2,-1); tot=cnt=0; } struct graph{ int to,Next; int id; ll w; }gra[maxn<<1],rgra[maxn]; void add1(int u,int v,ll w,int id){ gra[++tot].to=v; gra[tot].w=w; gra[tot].Next=h1[u]; gra[tot].id=id; h1[u]=tot; } void add2(int u,int v,ll w){ rgra[++cnt].to=v; rgra[cnt].w=w; rgra[cnt].Next=h2[u]; h2[u]=cnt; } struct node{ int to; ll dis; friend bool operator<(const node &a,const node &b){ return a.dis>b.dis; } }st,ed; void dij(){ clr(dis1,0x3f); clr(vis,0); dis1[1]=0; priority_queue<node>q; q.push({1,0}); while(!q.empty()){ st=q.top(); q.pop(); int u=st.to; if(vis[u])continue; vis[u]=1; for(int i=h1[u];i!=-1;i=gra[i].Next) { int v=gra[i].to; if(dis1[v]>dis1[u]+gra[i].w){ dis1[v]=dis1[u]+gra[i].w; q.push({v,dis1[v]}); } } } } void rdij(){ clr(dis2,0x3f); clr(vis,0); dis2[2]=0; priority_queue<node>q; q.push({2,0}); while(!q.empty()){ st=q.top(); q.pop(); int u=st.to; if(vis[u])continue; vis[u]=1; for(int i=h2[u];i!=-1;i=rgra[i].Next) { int v=rgra[i].to; if(dis2[v]>dis2[u]+rgra[i].w){ dis2[v]=dis2[u]+rgra[i].w; q.push({v,dis2[v]}); } } } } void tarjan(int u,int fa){ dfn[u]=low[u]=++tim; for(int i=h1[u];i!=-1;i=gra[i].Next) { int v=gra[i].to; if(dfn[v]==0){ tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]){ ans[gra[i].id]=1; } }else if(v!=fa){ low[u]=min(low[u],dfn[v]); } } } int main(){ while(cin>>n>>m){ init(); for(int i=1;i<=m;i++) { scanf("%d%d%lld",&a[i].from,&a[i].to,&a[i].w); mp[make_pair(make_pair(a[i].from,a[i].to),a[i].w)]++; a[i].id=i; add1(a[i].from,a[i].to,a[i].w,a[i].id); add2(a[i].to,a[i].from,a[i].w); } dij(); rdij(); clr(h1,-1),tot=0; for(int i=1;i<=m;i++) { // printf("i:%d dis1:%d dis2:%d dis:%d w:%d ",i,dis1[a[i].from],dis2[a[i].to],dis1[2],a[i].w); if(dis1[a[i].from]+dis2[a[i].to]+a[i].w==dis1[2]){ // printf("u:%d v:%d w:%d ",a[i].from,a[i].to,a[i].w); add1(a[i].from,a[i].to,a[i].w,a[i].id); add1(a[i].to,a[i].from,a[i].w,a[i].id); } } for(int i=1;i<=n;i++) { if(!dfn[i])tarjan(i,0); } for(int i=1;i<=m;i++) { int u=a[i].from,v=a[i].to; ll w=a[i].w; if(dis1[v]+w+dis2[u]<dis1[2]){ puts("HAPPY"); }else if(dis1[v]+w+dis2[u]==dis1[2]){ puts("SOSO"); }else { // printf("ans:%d mp:%d ",ans[i],mp[make_pair(make_pair(a[i].from,a[i].to),a[i].w)]); if(ans[i]&&mp[make_pair(make_pair(a[i].from,a[i].to),a[i].w)]==1){ // printf("debug1 "); puts("SAD"); } else { // printf("debug2 "); puts("SOSO"); } } } } }
补题：zz
题意：有两只虫，初始都在正四面体的A点，正四面体的边长为1，给定它们的爬行方向，问t时间后两只虫会不会在同一面上。
思路：把正四面体用一维平面来表示（有很多小的正三角形（边长为1）拼成的一个大的正三角形），小虫初始在这个大的正三角形的一个顶点上，可以根据给定的角度算出虫子的最终位置在哪，再算出它在第几行的第几个小的正三角形上，这些小的正三角形的分布都是有规律的，很容易看出来，再算出这个小的正三角形对应的是正四面体的哪一面。
//#pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<string> #include<math.h> #include<cmath> #include<time.h> #include<map> #include<set> #include<vector> #include<queue> #include<algorithm> #include<numeric> #include<stack> #include<bitset> #include<unordered_map> const int maxn = 0x3f3f3f3f; const double EI = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354594571382178525166427; const double PI = 3.141592653589793238462643383279; //#ifdef TRUETRUE //#define gets gets_s //#endif using namespace std; char dir[15]; double angle, dis, h, l; double sq3 = sqrt(3.0); int a1, a2; inline void counthl() { double a; a = fabs(30.0 - angle); h = dis * cos(PI * a / 180.0); l = dis * sin(PI * a / 180.0); if (angle < 30) { l = -l; } } inline int solve(void) { double cha, hen, cha2; counthl(); a1 = (int)h + 1; a1 = 0; double hh = h; while (hh > sq3 / 2) { hh -= sq3 / 2; a1++; } a1++; if (a1 % 2 == 1) { cha = hh; hen = cha / sq3; if (fabs(l) < hen) { a2 = 0; } else { /*cha2 = fabs(l) - hen; a2 = (int)cha2 + 1;*/ cha2 = fabs(l) - hen; a2 = ((int)cha2) * 2 + 1; double tmp = 1 - 2 * hen; cha2 -= (int)cha2; if (cha2 > tmp) { a2++; } if (l < 0) { a2 = -a2; } } } else { cha = sq3 / 2.0 - hh; hen = cha / sqrt(3.0); //printf("hen = %f ",hen); if (fabs(l) < hen) { a2 = 0; } else { cha2 = fabs(l) - hen; a2 = ((int)cha2) * 2 + 1; double tmp = 1 - 2 * hen; cha2 -= (int)cha2; if (cha2 > tmp) { a2++; } //printf("*** a2 = %d,cha2 = %f ",a2,cha2); if (l < 0) { a2 = -a2; } } } int a22 = a2; if (a2 < 0) { a2 = -a2; } if (l < 0) { a22 = -a2; } //printf("a1 = %d a2 = %d h = %f l = %f %d ",a1,a2,h,l,a22); if (dir[0] == 'B' && dir[1] == 'C') { if (a1 % 4 == 1 && a2 % 4 == 0 || a1 % 4 == 2 && a2 % 4 == 2 || a1 % 4 == 3 && a2 % 4 == 2 || a1 % 4 == 0 && a2 % 4 == 0) { return 1; } else if (a1 % 4 == 1 && a2 % 4 == 2 || a1 % 4 == 2 && a2 % 4 == 0 || a1 % 4 == 3 && a2 % 4 == 0 || a1 % 4 == 0 && a2 % 4 == 2) { return 4; } else if (a1 % 4 == 1 && (a22 < 0 && a2 % 4 == 1 || a22 > 0 && a2 % 4 == 3) || a1 % 4 == 2 && (a22 < 0 && a2 % 4 == 1 || a22 > 0 && a2 % 4 == 3) || a1 % 4 == 3 && (a22 > 0 && a2 % 4 == 1 || a22 < 0 && a2 % 4 == 3) || a1 % 4 == 0 && (a22 > 0 && a2 % 4 == 1 || a22 < 0 && a2 % 4 == 3)) { return 2; } else { return 3; } } else if (dir[0] == 'C' && dir[1] == 'D') { if (a1 % 4 == 1 && a2 % 4 == 0 || a1 % 4 == 2 && a2 % 4 == 2 || a1 % 4 == 3 && a2 % 4 == 2 || a1 % 4 == 0 && a2 % 4 == 0) { return 3; } else if (a1 % 4 == 1 && a2 % 4 == 2 || a1 % 4 == 2 && a2 % 4 == 0 || a1 % 4 == 3 && a2 % 4 == 0 || a1 % 4 == 0 && a2 % 4 == 2) { return 4; } else if (a1 % 4 == 1 && (a22 < 0 && a2 % 4 == 1 || a22 > 0 && a2 % 4 == 3) || a1 % 4 == 2 && (a22 < 0 && a2 % 4 == 1 || a22 > 0 && a2 % 4 == 3) || a1 % 4 == 3 && (a22 > 0 && a2 % 4 == 1 || a22 < 0 && a2 % 4 == 3) || a1 % 4 == 0 && (a22 > 0 && a2 % 4 == 1 || a22 < 0 && a2 % 4 == 3)) { return 1; } else { return 2; } } else { if (a1 % 4 == 1 && a2 % 4 == 0 || a1 % 4 == 2 && a2 % 4 == 2 || a1 % 4 == 3 && a2 % 4 == 2 || a1 % 4 == 0 && a2 % 4 == 0) { return 2; } else if (a1 % 4 == 1 && a2 % 4 == 2 || a1 % 4 == 2 && a2 % 4 == 0 || a1 % 4 == 3 && a2 % 4 == 0 || a1 % 4 == 0 && a2 % 4 == 2) { return 4; } else if (a1 % 4 == 1 && (a22 < 0 && a2 % 4 == 1 || a22 > 0 && a2 % 4 == 3) || a1 % 4 == 2 && (a22 < 0 && a2 % 4 == 1 || a22 > 0 && a2 % 4 == 3) || a1 % 4 == 3 && (a22 > 0 && a2 % 4 == 1 || a22 < 0 && a2 % 4 == 3) || a1 % 4 == 0 && (a22 > 0 && a2 % 4 == 1 || a22 < 0 && a2 % 4 == 3)) { return 3; } else { return 1; } } } int main(void) { //ios::sync_with_stdio(false); int z1, z2; scanf("%s %lf %lf", dir, &angle, &dis); z1 = solve(); scanf("%s %lf %lf", dir, &angle, &dis); z2 = solve(); //printf("z1 = %d z2 = %d ", z1, z2); if (z1 == z2) { printf("YES "); } else { printf("NO "); } return 0; }
I Starting a Scenic Railroad Service
Thinking：pai爷 kk
Code：kk 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=200010; struct node { int a,b; friend bool operator <(const node &x,const node &y) { return x.a<y.a; } } p[maxn]; int n; multiset<int >s; multiset<int >::iterator it; int ans2=0,ans1=0,a[maxn],b[maxn]; void anss2() { sort(p+1,p+1+n); s.insert(0); for(int i=1; i<=n; i++) { it=lower_bound(s.begin(),s.end(),p[i].a); if(it==s.begin()) { s.insert(p[i].b-1); } else { it--; s.erase(it); s.insert(p[i].b-1); } } } void anss3(){ int i; sort(p+1,p+1+n); priority_queue<int>q; q.push(-p[1].b + 1); ans2 = 1; for(i = 2;i <= n;i++) { //printf(" %d %d ",p[i].a,-q.top()); int pos = q.top(); pos = -pos; if(p[i].a > pos) { q.pop(); q.push(-p[i].b + 1); } else { ans2++; q.push(-p[i].b + 1); } } } void anss1() { for(int i=1;i<=n;i++) { a[p[i].a]++; b[p[i].b]++; } for(int i=1;i<=100000;i++) a[i]=a[i-1]+a[i],b[i]=b[i-1]+b[i]; for(int i=1;i<=n;i++) { ans1=max(ans1,a[p[i].b-1]-b[p[i].a]); } } int main() { while(cin>>n) { s.clear(); for(int i=1; i<=n; i++) { scanf("%d%d",&p[i].a,&p[i].b); } //anss2(); anss3(); anss1(); //ans2=s.size(); printf("%d %d ",ans1,ans2); } }
反思：
zz：理解方法慢了一些，没有理解pai爷的思路，第一遍代码写挂了，第二遍本应该ac的代码，写错了0到n-1和1到n，拖延了半个小时左右。（确定自己实现队友想出的思路的时候，理解的是正确的）
kk：B题样例没读懂。I题不知道multiset还存在被卡时间的可能。（换个人打，另外两个人讨论）
pai爷：处理前缀和时i从0开始，数组越界；int类型输出lld，C题样例没读懂。（看题看的慢一点，交代码的时候检查细节）