第二场(36)
过：EFH
补：AD
A题：
https://vjudge.net/contest/638726#problem/A
题意：有n张票和m个队伍，每一张票都有默认的对象，第一个队伍可以通过花一定量的金币把票买给自己，每张票需要的金币数不一样；
思路：枚举第一队赢的时候的投票数，其他队大于或等于该票数的一定反水，把没有反水的票集中在一起，如果还是不够的话从没有反水的票中取代价最小的
代码：
#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=3e3+10;
vector<LL> p[N];
LL len[N];
LL n,m;
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
LL x,y;
cin>>x>>y;
p[x].push_back(y);
}
for(int i=1;i<=m;i++)
{
len[i]=p[i].size();
sort(p[i].begin(),p[i].end());
}
LL ans=1e18;
for(LL i=1;i<=n;i++)
{
vector<LL> last;
LL cnt=len[1];
LL sum=0;
for(LL j=2;j<=m;j++)
{
if(len[j]>=i)
{
LL k=len[j]-i+1;
for(LL o=0;o<k;o++)
{
sum+=p[j][o];
}
cnt+=k;
for(LL o=k;o<len[j];o++)last.push_back(p[j][o]);
}
else
{
for(LL o=0;o<len[j];o++)last.push_back(p[j][o]);
}
}
if(cnt<i)
{
sort(last.begin(),last.end());
LL k=i-cnt;
for(int o=0;o<k;o++)
{
sum+=last[o];
}
}
ans=min(sum,ans);
}
cout<<ans<<endl;
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
B题：不会
https://vjudge.net/contest/638726#problem/B
C题：不会
https://vjudge.net/contest/638726#problem/C
D题：
https://vjudge.net/problem/CodeForces-618C
题意：一个包含很多点的散点图，取三个不共线的点连接成一个三角形，使得图内其他点都在该三角形外面；
思路：先按照x轴从小到大，y轴从小到大的顺序排序点，然后随机取三个距离最近的点，然后判断三点是否共线，如果不共线，则为答案；
代码：
#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
typedef long long LL;
typedef pair<double,double> PII;
const int N=1e5+10;
PII num[N];
bool cmp(PII a,PII b)
{
if(a.first!=b.first)
{
return a.first<b.first;
}
else
{
return a.second<b.second;
}
}
void solve()
{
int n;
cin>>n;
map<PII,int> op;
for(int i=0;i<n;i++)
{
cin>>num[i].first>>num[i].second;
op[num[i]]=i+1;
}
sort(num,num+n,cmp);
for(int i=0;i<n-2;i++)
{
double x1=num[i].first,y1=num[i].second;
double x2=num[i+1].first,y2=num[i+1].second;
double x3=num[i+2].first,y3=num[i+2].second;
if((x1==x2&&x2==x3)||(y1==y2&&y2==y3))continue;
if((y2-y1)/(x2-x1)==(y3-y1)/(x3-x1))continue;
cout<<op[num[i]]<<" "<<op[num[i+1]]<<" "<<op[num[i+2]]<<endl;
break;
}
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
E题：
https://vjudge.net/contest/638726#problem/E
题意：给定一个无序数组，目标是通过把下标排为升序从而使得整个数组升序
思路：可以证明，先复制一份原数组，sort为升序，然后把排好序数组的下标映射到排好的元素，然后到原数组中用原数组下标和映射下标用并查集连接，最后输出区间的个数以及区间的内容，输出模块可以用vector的二维数组完成，也可以用邻接表存储输出。
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <map>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
const int N=1e5+10;
typedef pair<LL,LL>PII;
LL num[N];
LL tmp[N];
LL pp[N];
LL e[N],ne[N],h[N],idy=0;
int idx=0;
int found(int b)
{
if(pp[b]!=b)pp[b]=found(pp[b]);
return pp[b];
}
void add(LL x,LL y)
{
e[idy]=y;
ne[idy]=h[x];
h[x]=idy++;
}
void solve()
{
int n;
map<LL,int> p;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>num[i];
pp[i]=i;
tmp[i]=num[i];
}
sort(tmp+1,tmp+n+1);
for(int i=1;i<=n;i++)p[tmp[i]]=i;
set<LL> used;
for(int i=1;i<=n;i++)
{
int a,b;
a=i;
b=p[num[i]];
if(a==b)continue;
pp[a]=found(b);
}
map<int,int> has;
for(int i=1;i<=n;i++)
{
int a=found(i);
used.insert(a);
has[a]++;
}
//for(int i=1;i<=n;i++)cout<<pp[i]<<endl;
cout<<used.size()<<endl;
//for(auto x:used)cout<<x<<"*"<<endl
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
add(found(i),i);
}
for(auto x:used)
{
cout<<has[x]<<" ";
for(LL i=h[x];i!=-1;i=ne[i])
{
LL k=e[i];
cout<<k<<" ";
}
cout<<endl;
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
F题：
https://vjudge.net/contest/638726#problem/F
题意:给定一个由’<’(向左)和’>’(向右)组成的地图，每一格都有对应的数组，代表这一步需要走的步数，判断这一生如履薄冰的我是否能够从左边走到对岸；
题解：之间dfs(),加一个一维st[]判断这个格子是否走过，如果有重复走格子，说明到不了对岸
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <map>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
const int N=1e5+10;
typedef pair<LL,LL>PII;
LL num[N];
LL tmp[N];
LL pp[N];
LL e[N],ne[N],h[N],idy=0;
int idx=0;
int found(int b)
{
if(pp[b]!=b)pp[b]=found(pp[b]);
return pp[b];
}
void add(LL x,LL y)
{
e[idy]=y;
ne[idy]=h[x];
h[x]=idy++;
}
void solve()
{
int n;
map<LL,int> p;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>num[i];
pp[i]=i;
tmp[i]=num[i];
}
sort(tmp+1,tmp+n+1);
for(int i=1;i<=n;i++)p[tmp[i]]=i;
set<LL> used;
for(int i=1;i<=n;i++)
{
int a,b;
a=i;
b=p[num[i]];
if(a==b)continue;
pp[a]=found(b);
}
map<int,int> has;
for(int i=1;i<=n;i++)
{
int a=found(i);
used.insert(a);
has[a]++;
}
//for(int i=1;i<=n;i++)cout<<pp[i]<<endl;
cout<<used.size()<<endl;
//for(auto x:used)cout<<x<<"*"<<endl
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
add(found(i),i);
}
for(auto x:used)
{
cout<<has[x]<<" ";
for(LL i=h[x];i!=-1;i=ne[i])
{
LL k=e[i];
cout<<k<<" ";
}
cout<<endl;
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
G题：TLE了，正在学习时间复杂度更低的方法
https://vjudge.net/contest/638726#problem/G
H题：
https://vjudge.net/problem/CodeForces-346A
题意：A和B博弈，在一个数组里面放入两个元素的距离，不能重复，如果谁放不了了，输；
思路：找到能放的最多数字，暴力查找数组里的最大公共因子m，数组最大容量等于数组最大值/n,减去原有数量得到能够放入的数量，判断奇偶即可。
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <map>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
const int N=1e2+10,M=1e8;
typedef pair<LL,LL>PII;
LL num[N];
bool st[M];
LL idx=0;
LL primes[N];
int n;
void get_primes(LL minn)
{
if(minn=1)return;
for(LL i=2;i<=minn;i++)
{
if(!st[i])
{
primes[idx++]=i;
for(LL j=i;j<=minn;j+=i)
{
st[j]=true;
}
}
}
}
bool check(LL a)
{
for(LL i=0;i<n;i++)
{
if(num[i]%a!=0)return false;
}
return true;
}
void solve()
{
cin>>n;
for(LL i=0;i<n;i++)cin>>num[i];
sort(num,num+n);
LL minn=num[0],maxx=num[n-1];
for(LL i=1;i<=n-1;i++)
{
minn=min(num[i]-num[i-1],(LL)minn);
}
get_primes(minn);
LL idy=0;
LL res=1;
for(LL j=1;j<=minn;j++)
{
if(minn%j!=0)
{
continue;}
if(check(j))res=max(res,j);
}
int cnt=maxx/res;
//cout<<cnt-n<<endl;
if((cnt-n)%2==0)puts("Bob");
else puts("Alice");
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
