痛苦死了，晚上降智严重。
我以为这是个死群。(昨晚被拉的)
哇我感觉我受到了很大的欺骗，
#睡醒午觉看手机，大家全都在写题。
哇结合“这也太紧凑了吧，昨天的题还没补完”，我瞬间脑补了一个 实验室众人已经连续好几个月保持每天x套题的高强度训练并且经常在群里讨论各种神仙题，而我却被蒙在鼓里还每天玩的很欢乐，大家的水平不知道高出我多少倍，一只手敲代码都吊打我，的场景。
我都没赖床直接打开待做输入场号点击vp开始表演小品。
算是第一个单切的四星场，水题不少，目前一共写了9个。打得太烂了，题面又长，又吃了个晚饭，M又看错题意自闭了一个多小时，导致好多题直接没看，，。
话说计科那边竟然能9题了。。还是感觉很厉害的啊。同期学长也是9题的样纸。。欸不过我单切嘛qwq，况且发挥好其实能8题(强行解释)
upd：九道题全tm水题，卧佛了，
A：去年新生赛就做过还做出来了，本来也是个沙比题。。
1 #include <bits/stdc++.h> 2 #define pi 3.14159265358979323846 3 typedef long long ll; 4 using namespace std; 5 const int N = 1e5+5; 6 double n,m,r,sx,sy,ex,ey; 7 int main(){ 8 //ios::sync_with_stdio(false); 9 cin>>n>>m>>r>>sx>>sy>>ex>>ey; 10 double a1=abs(ey-sy)/m*r; 11 double a2=abs(sx-ex)/n*r*pi*min(sy,ey)/m; 12 double ans1=a1+a2; 13 double ans2 = (ey+sy)/m*r; 14 double ans = min(ans1,ans2); 15 printf("%.10f ",ans); 16 }
C：沙比题直接暴力。当时一眼就直接暴力，结果有个地方写错了T了两发
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int N = 5e5+5; 5 inline int read() { 6 int X=0,w=1; char c=getchar(); 7 while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } 8 while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); 9 return X*w; 10 } 11 ll gcd(ll a,ll b){ 12 return b==0?a:gcd(b,a%b); 13 } 14 int n;ll a[N],b[N];int cnt=0; 15 set<ll>s[N]; 16 int main(){ 17 n=read(); 18 for(int i=1;i<=n;i++) { 19 scanf("%lld",&a[i]); 20 if(a[i]!=a[i-1]) 21 b[cnt++]=a[i]; 22 } 23 for(int i=cnt-1;i>=0;i--){ 24 ll tmp = b[i]; 25 s[i].insert(tmp); 26 for(int j=i+1;j<cnt;j++){ 27 tmp = gcd(tmp,b[j]); 28 if(s[j].count(tmp)) 29 break; 30 s[i].insert(tmp); 31 } 32 } 33 set<ll>ans;ans.clear(); 34 for(int i=0;i<cnt;i++){ 35 for(auto t:s[i]) 36 ans.insert(t); 37 } 38 //printf("%d ",ans.size()); 39 cout<<ans.size()<<endl; 40 }
D：dijkstra板子题。又没读懂题意读了好久好久。 到终点最短的那条路不能走。。。
#include <bits/stdc++.h> typedef long long ll; using namespace std; inline int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); return X*w; } const int N = 1e5+5; struct Edge { int v,w,nxt; }; Edge e[1000010]; int head[200010],cnt=0; inline void addEdge(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].nxt=head[u]; head[u]=cnt; } int n,m,s=1; int dis[100010]; struct node { //堆节点 int u,d; bool operator <(const node& rhs) const { return d>rhs.d; } }; void Dijkstra() { for (int i=0;i<n;i++) dis[i]=2147483647; dis[s]=0; priority_queue<node> Q; //堆 Q.push((node){s,0}); while (!Q.empty()) { node fr=Q.top(); Q.pop(); int u=fr.u,d=fr.d; if (d>dis[u]) continue; for ( int i=head[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if (dis[u]+w<dis[v]) { dis[v]=dis[u]+w; Q.push((node){v,dis[v]}); } } } } int vis[N],ans[N]; void dfs(int u,int id){ vis[u]=1; ans[id]=u; if(u==1){ cout<<id<<' '; for(int i=1;i<=id;i++) cout<<ans[i]<<' '; exit(0); } for(int i=head[u];i;i=e[i].nxt){ int v=e[i].v,w=e[i].w; if(w+dis[v]==dis[u]) continue; if(vis[v])continue; dfs(v,id+1); } } int main(){ n=read();m=read(); int x,y,z; while (m--){ x=read();y=read();z=read(); addEdge(x,y,z);addEdge(y,x,z); } Dijkstra(); dfs(0,1); cout<<"impossible"<<endl; }
E：二分+二分图匹配。我比赛的时候又没时间看这道题啊。感觉好水啊，，，搜题解还搜到了同学的。。。还是人家去年暑假写的题解，，为什么我这么菜啊www，我纸币惹。
显然二分距离然后加边，跑二分图匹配，显然如果一对 b,r 能匹配上那么这两个盒子我们就不能同时用吧，也就是说至多这两个 b,r 只能选一个。
所以只要满足 b+r-匹配数>=n 就行了
1 #include <bits/stdc++.h> 2 #define db long double 3 typedef long long ll; 4 using namespace std; 5 const int N = 1e5+5; 6 struct Node{ 7 int x,y; 8 }a[255],c[255]; 9 double d[255][255]; 10 double dis(int x,int y){ 11 return sqrt(abs(c[y].x-a[x].x)*abs(c[y].x-a[x].x)+abs(c[y].y-a[x].y)*abs(c[y].y-a[x].y)); 12 } 13 int g[255][255]; 14 int linker[256],used[256]; 15 int n,b,r; 16 bool dfs(int u){ 17 for(int v=1;v<=r;v++){ 18 if(g[u][v]&&!used[v]){ 19 used[v]=true; 20 if(linker[v]==-1||dfs(linker[v])){ 21 linker[v]=u; 22 return true; 23 } 24 } 25 } 26 return false; 27 } 28 int hungry(){ 29 int res=0; 30 memset(linker,-1, sizeof(linker)); 31 for(int u=1;u<=b;u++){ 32 memset(used,0, sizeof(used)); 33 if(dfs(u)) 34 res++; 35 } 36 return res; 37 38 } 39 int check(double x){ 40 memset(g,0, sizeof(g)); 41 for(int i=1;i<=b;i++){ 42 for(int j=1;j<=r;j++) { 43 if(d[i][j]<=x){ 44 g[i][j]=1; 45 } 46 } 47 } 48 return b+r-n>=hungry(); 49 } 50 int main(){ 51 ios::sync_with_stdio(false); 52 cin>>n>>b>>r; 53 for(int i=1;i<=b;i++){ 54 cin>>a[i].x>>a[i].y; 55 } 56 for(int i=1;i<=r;i++){ 57 cin>>c[i].x>>c[i].y; 58 } 59 for(int i=1;i<=b;i++){ 60 for(int j=1;j<=r;j++){ 61 d[i][j]=dis(i,j); 62 } 63 } 64 double l=0,r=1e6; 65 while (l+1e-9<r){ 66 double mid=(l+r)/2; 67 if(check(mid)){ 68 l=mid; 69 } else{ 70 r=mid; 71 } 72 } 73 printf("%.9f",l); 74 }
F：。。。
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int N = 1e5+5; 5 int a[N],n; 6 int main(){ 7 ios::sync_with_stdio(false); 8 cin>>n; 9 int sum = 0; 10 for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i]; 11 sort(a+1,a+1+n); 12 reverse(a+1,a+1+n); 13 int ans =0; 14 for(int i=1;i<=n;i+=2){ 15 ans+=a[i]; 16 } 17 cout<<ans<<' '<<sum-ans<<endl; 18 }
I：。。。我纠结了四个小时题意。。这个南北东西都是什么啊。。。真实自闭。还有切的位置什么的。。。其实瞎猜就行(大雾
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int N = 1e5+5; 5 int n,m; 6 int main(){ 7 //cnm这题什么题意啊？？？？ 8 ios::sync_with_stdio(false); 9 cin>>n>>m; 10 if(n&1){ 11 if(m&1){ 12 cout<<1; 13 } else{ 14 if(n<m) 15 cout<<2; 16 else 17 cout<<0; 18 } 19 } else{ 20 if(m&1){ 21 cout<<0; 22 } else{ 23 cout<<0; 24 } 25 } 26 }
K：我没做出来。不会搜索。不是这个题怎么可以这么傻逼啊，为什么我还不会啊。我怎么这么傻逼啊。一开始拓扑排序了一遍wa了就没啥思路了。。。
bfs确实存在一些问题，比方说很多叉？ dfs就保证是连续的？哎呀我神志不清。
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int N = 1e5+5; 5 int n;char g[1005][1005]; 6 int vis[N],ans[N],cnt; 7 void dfs(int now){ 8 vis[now]=1; 9 ans[cnt++]=now; 10 if(cnt==n){ 11 for(int i=cnt-1;i>=0;i--){ 12 cout<<ans[i]<<' '; 13 } 14 exit(0); 15 } 16 for(int i=1;i<n;i++){ 17 if(g[now][i]=='1'&&!vis[i]){ 18 dfs(i); 19 } 20 } 21 } 22 int main(){ 23 ios::sync_with_stdio(false); 24 cin>>n; 25 for(int i=0;i<n;i++){ 26 for(int j=0;j<n;j++){ 27 cin>>g[i][j]; 28 } 29 } 30 dfs(0); 31 cout<<"impossible"; 32 }
L：卡精，所以我们取对数，也好像不卡？不知道。中间一度wa到自闭，刚才忽然想到取完对数之后可以小于0，然后我直接取的max。。。就是没有判断 count()。。。
真自闭哇。话说 In 和 log 有什么区别么。。。
#include <bits/stdc++.h> #define db long double typedef long long ll; using namespace std; const int N = 1e5+5; const db eps = 1e-15; int sign(db a){ return a<-eps?-1:a>eps;} int cmp(db a,db b){ return sign(a-b);} int n;string o,w;//... db _max(db a,db b){ if(cmp(a,b)==1)return a; return b; } db x; map<string,db>mp; int main(){ cin>>n; mp["pink"]=0.0; for(int i=1;i<=n;i++){ cin>>o>>w>>x; db tmp = log(x); if(mp.count(w)) { if(mp.count(o)) mp[o] = _max(mp[o], mp[w] + tmp); else mp[o] = mp[w] + tmp; } } if(mp.count("blue")) { db ans = exp(mp["blue"]); if (ans-10>1e-8) { cout << 10 << endl; } else { cout << fixed << setprecision(15) << ans << endl; } } else cout<<0<<endl; }
M：绝世傻逼题，我写了一个半小时。一开始理解错了。。以为是那种树状数组维护的那种奇怪的东西。自闭。
然后发现是个LIS，然后又自闭了，最后发现是cmp写错了。。。忘记第二维也要按顺序，反正我是自闭了。+16真是可喜可贺啊
1 #include <bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 const int N = 1e5+5; 5 struct Node{ 6 int x,y; 7 }node[N]; 8 bool cmp1(Node a,Node b){ 9 if(a.x==b.x) return a.y<b.y; 10 return a.x<b.x; 11 } 12 bool cmp2(Node a,Node b){ 13 if(a.x==b.x) return a.y<b.y; 14 return a.x>b.x; 15 } 16 int n,sx,sy,ex,ey; 17 int a[N],cnt; 18 int main(){//救命啊 19 ios::sync_with_stdio(false); 20 cin>>n>>sx>>sy>>ex>>ey; 21 for(int i=1;i<=n;i++){ 22 cin>>node[i].x>>node[i].y; 23 } 24 if(sx>ex) { 25 swap(sx, ex); 26 swap(sy, ey); 27 } 28 if(sx<=ex&&sy<=ey){ 29 sort(node + 1, node + 1 + n, cmp1); 30 for(int i=1;i<=n;i++){ 31 if(node[i].x<sx||node[i].x>ex)continue; 32 if(node[i].y<sy||node[i].y>ey)continue; 33 if(cnt==0||node[i].y>=a[cnt-1]){ 34 a[cnt++]=node[i].y; 35 } else{ 36 int id = upper_bound(a,a+cnt,node[i].y)-a; 37 a[id]=node[i].y; 38 } 39 } 40 } else if(sx<=ex&&sy>=ey){ 41 sort(node + 1, node + 1 + n, cmp2); 42 for(int i=1;i<=n;i++){ 43 if(node[i].x<sx||node[i].x>ex)continue; 44 if(node[i].y<ey||node[i].y>sy)continue; 45 if(cnt==0||node[i].y>=a[cnt-1]){ 46 a[cnt++]=node[i].y; 47 } else{ 48 int id = upper_bound(a,a+cnt,node[i].y)-a; 49 a[id]=node[i].y; 50 } 51 } 52 } 53 cout<<cnt<<endl; 54 }
哦顺便嘲讽一下某紫名选手C题卡了三个多小时+7。喜闻乐见啊！
要死了要死了睡觉睡觉。