第三场
(ac+补)6题：ACDEGI
A题：
https://vjudge.net/contest/638592#problem/A
题意：多矿工挖矿，n个矿工和矿山，矿工全在y轴上，矿山全在x轴上，一个矿工只能挖一个矿山，消耗的能量为矿工和矿山的距离，求消耗最小的能量
思路：全部sort一遍，一一对应求距离，加起来就是最小值
(这里踩了一个坑，数据范围为1e8到-1e8，如果用double平方的话会爆double，要先用long long平方完后sqrt)
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
typedef long long LL;//开long long，切记，切记，切记！
typedef pair<double,double> PII;
const LL N=1e5+10;
LL all[N];
LL coin[N];
double abss(double a)
{
if(a<0)a*=-1;
return a;
}
bool cmd(PII a,PII b)
{
if(a.second==0)
{
return a.first>b.first;
}
else return a.second>b.second;
}
double work(LL y1,LL x2)
{
double dist=y1*y1+x2*x2;
return sqrt(dist);
}
void solve()
{
int u;
cin>>u;
int idx=0;
int idy=0;
for(int i=0;i<2*u;i++)
{
LL x,y;
cin>>x>>y;
if(x<0)x*=-1;
if(y<0)y*=-1;
if(x==0)all[idx++]=y;
else coin[idy++]=x;
}
//cout<<idx<<idy<<endl;
sort(all,all+u);
sort(coin,coin+u);
double sum=0;
for(int i=0;i<u;i++)
{
sum+=work(all[i],coin[i]);
}
printf("%.9llf\n",sum);
}
int main()
{
LL t;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>t;
while(t--)
{
solve();
}
return 0;
}
B题：不会
https://vjudge.net/problem/Gym-101239L
C题:
https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-1982
题意：给定n堆石子，每个人可以进行以下操作，从一个非空堆中拿出至少一个石子去掉，然后再拿任意数量个石子到其他非空堆，谁先无法移动(包括拿掉和拿给任意非空堆),谁就输；
思路:博弈论大guess题,second赢的条件，石子能够分成完全相同的两份，first对一份进行操作，second对另一份复制操作；其余情况下first赢；
代码：
#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<LL,LL> PII;//开long long，求求你了，记得开long long
const LL N=1e5+10;
const LL INF=1e18;
const double small=1e-16;
//千万不要用puts()和gets()，求求你了
LL num[N];
void solve()
{
LL n;
cin>>n;
set<LL> has;
map<LL,LL> ans;
if(n%2==1)
{
puts("first player");
return;
}
for(int i=1;i<=n;i++)
{
cin>>num[i];
has.insert(num[i]);
ans[num[i]]++;
}
for(auto x:has)
{
if(ans[x]%2==1)
{
puts("first player");
return;
}
}
puts("second player");
}
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;
}
D题：(最涨血压的一题，puts()我恨你)
https://vjudge.net/problem/CodeForces-981C
题意：给定一个无向无环图，判断能否把这个图分解为若干个简单路径，这些路径都有一个共同端点
思路:统计每个节点与其相连的节点数有多少，如果节点数大于2的节点超过1个，就不能成功分解；分解：以该节点出发，dfs找到另一个顶点然后输出即可
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
typedef long long LL;//开long long，切记，切记，切记！
typedef pair<LL,LL> PII;
const LL N=1e5+10;
PII has[N];
PII num[N];
LL e[2*N],ne[2*N],h[N],idx=0;
bool st[N];
void add(int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
LL dfs(int u,int fu)
{
int tim=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int k=e[i];
if(k==fu)continue;
return dfs(k,u);
}
return u;
}
void solve()
{
int n;
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<n;i++)
{
LL x,y;
cin>>x>>y;
has[i]={x,y};
num[i].second=i;
num[x].first++;
num[y].first++;
add(x,y);
add(y,x);
}
num[n].second=n;
sort(num+1,num+1+n);
if(num[n-1].first>=3)
{
cout<<"No"<<endl;//这里千万不能用puts(),可能是缓冲区出了问题，也可能是cin，cout解绑的问题，导致YES和NO全部输出到末尾，导致一直wa1，导致红温了好久
return;
}
else
{
cout<<"Yes"<<endl;
int mid=num[n].second;
st[mid]=true;
cout<<num[n].first<<"\n";
for(int i=h[mid];i!=-1;i=ne[i])
{
//puts("*");
int k=e[i];
cout<<mid<<" "<<dfs(k,mid)<<"\n";
}
}
}
int main()
{
LL t;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
t=1;
while(t--)
{
solve();
}
return 0;
}
E题：
https://vjudge.net/problem/CodeForces-485D
题意:给定一个数组a，求ai%aj的最大值，ai>aj
思路：sort数组，然后从最小值开始，枚举最大值以内的倍数，然后二分找到一个比该倍数大的第一个数，然后求余取大值
代码：
#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=2e5+10;
LL num[N];
void solve()
{
LL n;
cin>>n;
for(int i=1;i<=n;i++)cin>>num[i];
sort(num+1,num+1+n);
LL ans=0;
LL len=unique(num+1,num+1+n)-num-1;
for(int i=1;i<=len;i++)
{
for(LL j=num[i];j<=num[len];j+=num[i])
{
LL tmp=lower_bound(num+1,num+1+n,j+num[i])-num-1;
ans=max(ans,num[tmp]%num[i]);
}
}
cout<<ans<<endl;
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
F题：不会
https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-3832
G题：
题意：给定一个由小写字母组成的字符串，每个字母都需要改成相邻的另一种字母，由两个人轮流操作，a要字符串字典序尽可能小，b要字典序大,求改完后的字符串，a先手；
思路：a,如果是a，改成b，其他的字母减1
b，如果是z，改成y，其他字母加1
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
typedef long long LL;//开long long，切记，切记，切记！
typedef pair<LL,LL> PII;
const LL N=1e5+10;
void solve()
{
string s;
cin>>s;
int n=s.size();
for(int i=0;i<n;i++)
{
if(i%2==0)
{
if(s[i]=='a')s[i]='b';
else s[i]='a';
}
else
{
if(s[i]=='z')s[i]='z'-1;
else s[i]='z';
}
}
cout<<s<<endl;
}
int main()
{
LL t;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>t;
while(t--)
{
solve();
}
return 0;
}
H题：不会
https://vjudge.net/problem/AtCoder-abc350_g
I题：
https://vjudge.net/problem/CodeForces-727C
题意：好玩的交互题，目标是构造一个长度为n的数组，可以问n个问题，分别是两个元素的和
思路：数学推导一下就可以了
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
typedef long long LL;//开long long，切记，切记，切记！
typedef pair<LL,LL> PII;
const LL N=1e5+10;
LL n;
LL num[N];
LL res[N];
void solve()
{
cin>>n;
for(int i=1;i<=n-1;i++)
{
cout<<"? "<<i<<" "<<i+1<<endl;
fflush(stdout);
cin>>num[i];
}
if(n%2==1)
{
cout<<"? "<<"1"<<" "<<n<<endl;
fflush(stdout);
cin>>num[n];
LL sum=0;
for(int i=1;i<=n;i++)
{
if(i%2==1)sum+=num[i];
else sum-=num[i];
}
res[1]=sum/2;
}
else
{
cout<<"? "<<"1"<<" "<<"3"<<endl;
fflush(stdout);
cin>>num[n];
LL sum=(num[n]+num[1]-num[2]);
res[1]=sum/2;
}
for(int i=1,j=2;i<=n-1;i++,j++)
{
res[j]=num[i]-res[j-1];
}
cout<<"! ";
for(int i=1;i<=n;i++)cout<<res[i]<<" ";
puts("");
fflush(stdout);
}
int main()
{
LL t;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
t=1;
while(t--)
{
solve();
}
return 0;
}
J题：不会
https://vjudge.net/problem/CodeForces-1381C
K题：不会
https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-1915
