第一场(20)：
不会的先放链结，后面再补
A5题：BEFHI
补：J
A题：不会
https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-4771
B题：
https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-3399
题意：两个数列a和b，通过a的元素增加或减少（两者代价不同）来得到任意顺序的b，求最小代价；
思路：sort两个数列a、b，b-a得到一个差异序列，再进行加减使得差异数列全为0的代价最小
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
using namespace std;
const int N=3e5+10;
typedef long long LL;
typedef pair<LL,LL> PII;
LL a[N],b[N];
void solve()
{
LL n,x,y;
LL res=0;
cin>>n>>x>>y;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
}
sort(a,a+n);
sort(b,b+n);//任意顺序的b;
for(int i=0;i<n;i++)
{
if(a[i]>=b[i])
{
res+=(a[i]-b[i])*y;
}
else res+=(b[i]-a[i])*x;
}
cout<<res<<endl;
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
C题：不会
https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P3231
D题：不会
https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P2120
E题：
https://vjudge.net/contest/638591#problem/E
题意：博弈论题目,轮流在桌子上放盘子，盘子不能堆积，谁先放不下输；
思路：可以证明，当桌子可以放下至少一个盘子时，先手总是必胜的，所以只用判断长宽的最小值是否大于盘子直径；
坑：这里没有说盘子和桌子不能没有边界，所以不需要额外加上一个极小数
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
using namespace std;
const int N=1e5+10;
const double M=1e-8;//202325220708
typedef long long LL;
typedef pair<LL,LL> PII;
void solve()
{
double a,b,r;
cin>>a>>b>>r;
double change=2.0*r-sqrt(3.0)*r;
double idx=0;
if(a>=2*r&&b>=2*r)//这里因为想要处理精度问题加了一个极小数M=1e-8，导致wa了很多发
{
puts("First");
}
else puts("Second");
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
F题：
https://vjudge.net/contest/638591#problem/F
题意：给定一个数列a，按照一定的规则构造数列b：a1=b1，bi等于ai与a1到ai-1元素最近的距离；求数列b的和；
思路：1.枚举每个ai，找到ai前面最接近的点，把最小距离加在sum上；（TLE）
2.优化：枚举每个ai前，sort（a,a+i）,再用二分法找到最近点；（TLE）
3.枚举完ai后，把ai加入到set中，在枚举aj时，枚举距离（0——65536），找到最近距离，加入sum（AC）；
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
using namespace std;
const int N=65536+10,M=65536;
typedef long long LL;
typedef pair<LL,LL> PII;
int n;
void solve()
{
int n;
cin>>n;bool st[N]={false};
int x;
cin>>x;
LL res=x;
st[x]=true;
for(int i=0;i<n-1;i++)
{
int y;
cin>>y;
for(int i=0;i<=N;i++)
{
if(st[max(min(i+y,M),0)]||st[min(max(0,y-i),M)])
{
res+=i;
break;
}
}st[y]=true;
}
cout<<res<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
G题：不会
https://vjudge.net/problem/BZOJ-5296
H题：
https://vjudge.net/contest/638591#problem/H
题意：给定n，求0<=x<n的x满足：x^2=n*k+1(0<=k),从小到大输出：
思路：直接暴力枚举x，找到满足条件的x入set，去重（优化：有个看出来的规律，就是顺数第i个数和倒数第i个数的和等于常数，能够减少一半的枚举）
#include <iostream>
#include <cstring>
#include <algorithm>//1234
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
using namespace std;
const int N=1e5+10;
typedef long long LL;
typedef pair<LL,LL> PII;
LL num[N];
bool check(LL x)
{
double a=sqrt(x);
if(a==(LL)a)return true;
return false;
}
void solve()
{
LL n;
cin>>n;
set<LL> has;
for(LL i=0;i<=n/2;i++)//i记得开long long ，wa了好多发
{
if(i*i%n==1)has.insert(i),has.insert(n-i);//规律
}
if(has.size()==0)puts("None");
else for(auto x:has)
{
cout<<x<<endl;
}
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
I题：
https://vjudge.net/contest/638591#problem/I
题意：一堆不同颜色的牌，有n次询问，每次询问一个颜色，找到这个颜色牌的最小下标输出，并把这张牌放在牌堆顶部；
思路：纯纯大模拟题，用栈来维护牌堆，不断出栈找到目标颜色，在依次入栈，把目标颜色的牌放在牌堆顶；
#include <iostream>
#include <cstring>
#include <algorithm>//202325220708
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int N=1e6+10;
typedef long long LL;
typedef pair<LL,LL> PII;
int b[N],a[N];
int tmp[N];
void solve()
{
int n,m;
cin>>n>>m;
stack<int> q;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<m;i++)
{
cin>>b[i];
}
for(int i=n-1;i>=0;i--)
{
q.push(a[i]);
}
for(int i=0;i<m;i++)
{
int k=0;
while(q.top()!=b[i])
{
tmp[k++]=q.top();
q.pop();
}
q.pop();
cout<<k+1<<" ";
if(k!=0)
{
for(int j=k-1;j>=0;j--)
{
q.push(tmp[j]);
}
}
q.push(b[i]);
}
puts("");
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
J题:
https://vjudge.net/contest/638591#problem/J
题意：给一个无向图，在部分结点上设置基站，能够覆盖到当前节点和相邻节点，求覆盖掉整个图需要的最小基站数；
思路：树形dp问题，对于每个节点的状态，都可以用三个数字来表示：0-自己覆盖自己，1-子节点覆盖自己，2-父节点覆盖自己；
分析图：
#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=1e5+10;
int h[N],e[N],ne[N],idx=0;
int dp[N][3];//0自己，1子，2父
void add(int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
void dfs(int u,int f_u)
{
dp[u][0]=1;
dp[u][1]=0x3f3f3f3f;
dp[u][2]=0;
int sum=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int k=e[i];
if(k==f_u)continue;
dfs(k,u);
dp[u][0]+=min(dp[k][0],min(dp[k][1],dp[k][2]));
int p=min(dp[k][0],dp[k][1]);
sum+=p;
dp[u][2]+=p;
}
for(int i=h[u];i!=-1;i=ne[i])
{
int k=e[i];
if(k==f_u)continue;
dp[u][1]=min(dp[u][1],sum-min(dp[k][1],dp[k][0])+dp[k][0]);
}
}
void solve()
{
int n;
cin>>n;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,-1);
cout<<min(dp[1][0],dp[1][1])<<endl;
}
int main()
{
int t;
t=1;
while(t--)
{
solve();
}
return 0;
}
K题：
https://vjudge.net/contest/638591#problem/K
题意：给定一个数列，进行两个操作：1.从下标L到R增加W，2.询问在L到R之间大于K的数有多少个？
思路：1.暴力枚举，铁TLE
2.线段树，线段树在查询的时候只能一次查询一个，tle
3.分块，把数列分成一定大小的块，然后把每个块看成一个整体，每个块都有一个lazy数组存储应该加多少，然后再块内排序，用二分的方法找到大于等于k-lazy[i]的数量
//有一些细节方面的问题，导致wa了，待补
