Day 3Codeforces Round #558 (Div. 2)(A,B1,B2,C1,C2)

Codeforces Round #558 (Div. 2)

A:

思路:m个人离开后，还剩n-m个人，枚举1~(n-m）,看补上m个人是否能连成环

代码:

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+9; priority_queue<int>q; int main(){ int i,j,k,n,m; cin>>n>>m; if(n==m){ cout<<0<<endl; } else{ n-=m; for(i=n;i>=0;i--){ if(m>=i||i==1){ cout<<i<<endl; break; } } }

B1

思路:判断前1~i这段序列是否合法，取最大值，注意到若序列合法，则删去一天之后，不同颜色出现的次数全部一样，即最多只能有一个颜色出现的次数不一样，并且这个颜色出现的次数必须刚好比其他颜色出现的次数多1或这个颜色出现的次数就是1.对B1的数据范围，我们完全可以纯暴力，枚举每个颜色，若这个颜色出现的次数减一之后所有颜色出现的次数都一样(特判一些颜色出现次数减一等于0的情况)

代码:

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+9; int a[maxn],mp[maxn]; int cnt[maxn]; set<int>st,st2; int main(){ ios::sync_with_stdio(0); cin.tie(0); int i,j,k,n,m; cin>>n; int ans=1; for(i=1;i<=n;i++){ cin>>a[i]; mp[a[i]]++; st.insert(a[i]); for(auto it:st){ mp[it]--; int flag=0; int x=it; int u; for(auto iter:st){ if(mp[iter]!=0)u=mp[iter]; } for(auto iter:st){ if(mp[iter]==0||mp[iter]==u){ continue; } else{ flag=1; break; } } mp[it]++; if(!flag){ ans=i; break; } } } cout<<ans<<endl; }

B2:

思路:相比较B1，B2的颜色数据范围变大了，我们显然不能通过枚举颜色来解决问题。我们可以考虑声明一个set容器，维护颜色出现的次数，然后再开一个cnt数组储存这个序列颜色出现x次的有多少个颜色，每次将颜色出现次数插入到set容器的时候，对于我的这个程序而言，插入一u[i]颜色出现的次数时，需要撤销上次遍历到这个颜色时出现的次数的插入。处理完之后，只有当set的大小为2或为1时才可能合法，大小为2时，要么出现次数大的那个只有一个颜色出现过这么多次，并且次数只比其余颜色出现次数多1，要么次数小的那个颜色出现次数为1并且只有一个颜色出现过这么多次。大小为1时，只有出现次数这么多的颜色唯一或有多个颜色出现次数等于1时合法，有点绕

代码:

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+9; int a[maxn],mp[maxn]; int cnt[maxn]; set<int>st,ap_cnt; int main(){ ios::sync_with_stdio(0); cin.tie(0); int i,j,k,n,m; cin>>n; int ans=1; for(i=1;i<=n;i++){ cin>>a[i]; mp[a[i]]++; // st.insert(a[i]); cnt[mp[a[i]]]++; if(cnt[mp[a[i]]-1]!=0) cnt[mp[a[i]]-1]--; ap_cnt.insert(mp[a[i]]); if(cnt[mp[a[i]]-1]==0) ap_cnt.erase(mp[a[i]]-1); if(ap_cnt.size()==2){ int x=*ap_cnt.begin(),y=*++ap_cnt.begin(); // cout<<y<<' '<<cnt[y]<<endl; if(y-x==1&&(cnt[y]==1)||((cnt[x]==1&&x==1)))ans=i; } else if(ap_cnt.size()==1){ int x=*ap_cnt.begin(); if(x==1||cnt[x]==1)ans=i; } } cout<<ans<<endl; }

C1:

思路:思路很简单，找出所有的不一样的直线，根据斜率判断是否相交，相交答案+1，去重感觉有点麻烦

代码：

#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const int maxn=59; struct node{ int x,y,c; }a[maxn]; vector<node>line; map<tuple<int, int, int>,int>mp; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int main(){ int i,j,k,n; cin>>n; for(i=0;i<n;i++){ cin>>a[i].x>>a[i].y; } for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ int x1=a[i].x,x2=a[j].x; int y1=a[i].y,y2=a[j].y; int c=x2*y1-x1*y2; /*if(x1-x2==0){ if(!mp[{(x1-x2),(y2-y1),c}]){ line.push_back({(x1-x2),(y2-y1),c}); mp[{(x1-x2),(y2-y1),c}]=1; continue; } } else if(y2-y1==0){ if(!mp[{(x1-x2),(y2-y1),c}]){ line.push_back({(x1-x2),(y2-y1),c}); mp[{(x1-x2),(y2-y1),c}]=1; continue; } }*/ int d=gcd((x1-x2),(y2-y1)); int t2=(x1-x2)/d,t1=(y1-y2)/d; c=t1*x1-t2*y1; if(!mp[tie(t1,t2,c)]){ line.push_back({t1,t2,c}); mp[tie(t1,t2,c)]=1; } } } int len=line.size(),ans=0; // cout<<len<<endl; for(i=0;i<len;i++){ // cout<<line[i].x<<' '<<line[i].y<<' '<<line[i].c<<endl; for(j=i+1;j<len;j++){ if(line[i].x==line[j].x&&line[i].y==line[j].y){ continue; } ans++; } } cout<<ans<<endl; }

C2：

思路:这道题最多有1e6条边，不能暴力判断两条边是否相交了，我们可以找出每一个斜率的边数（截距不同）x，然后用(总的边数-x*)x,因为每一个斜率我们会重复计算一次，所以最后的答案我们要除以二。啊，感觉我的代码写的跟屎一样。

代码:

#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const int maxn=1e3+9; struct node{ int x,y,c; }a[maxn]; vector<node>line; map<tuple<int, int, int>,int>mp; map<pair<int,int>,int>mmp; int cnt[maxn]; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } set<int>st; int main(){ ios::sync_with_stdio(0); cin.tie(0); int i,j,k,n; cin>>n; for(i=0;i<n;i++){ cin>>a[i].x>>a[i].y; } for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ int x1=a[i].x,x2=a[j].x; int y1=a[i].y,y2=a[j].y; int c=x2*y1-x1*y2; int d=gcd((x1-x2),(y2-y1)); int t2=(x1-x2)/d,t1=(y1-y2)/d; c=t1*x1-t2*y1; if(!mp[tie(t1,t2,c)]){ mmp[{t1,t2}]++; cnt[mmp[{t1,t2}]]++; if(cnt[mmp[{t1,t2}]-1]!=0){ cnt[mmp[{t1,t2}]-1]--; } st.insert(mmp[{t1,t2}]); if(cnt[mmp[{t1,t2}]-1]==0){ st.erase(mmp[{t1,t2}]-1); } line.push_back({t1,t2,c}); mp[tie(t1,t2,c)]=1; } } } long long len=line.size(),ans=0; for(auto it:st){ //cout<<it<<endl; ans+=cnt[it]*it*(len-it*); } cout<<ans/2<<endl; }