A题
题目大意：比较$a \times n$与$b$的大小
这题还用说吗......没有坑点。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
using namespace std;
typedef long long ll;
int n,a,b;
int main(){
cin >>n>>a>>b;
cout<<min(n*a,b);
return 0;
}
B题
题目大意：给你$n$个$d$维空间上的点，求有多少点对使得这两个点之间的距离是正整数
这题也没有什么好说的，首先算距离的平方，之后只需要看是否”$sqrt$(距离)*$sqrt$(距离)$==$距离“即可（此时$sqrt$返回值用int存就行）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
using namespace std;
typedef long long ll;
int n,d;
int ans,sum;
int x[50][50];
int main(){
cin>>n>>d;
for(int i=1;i<=n;++i){
for(int j=1;j<=d;++j){
cin>>x[i][j];
}
}
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(i==j)continue;
int tmp=0;
for(int k=1;k<=d;++k){
tmp+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
}
int a=sqrt(tmp);
if(a*a==tmp)ans++;
}
}
cout<<ans;
return 0;
}
C题
题目大意：给出正整数$L$和$R$，找出正整数$i,j∈[L,R]$，使得$(i \times j) \bmod 2019$最小，输出最小值
这题我居然能WA四次......
首先可以特判：若$\frac{R}{2019}>\frac{L}{2019}$或$L=0$或$R=0$，说明$[L,R]$中一定有一个$2019$的倍数，此时直接输出$0$；
剩下来的情况就只有$\frac{L}{2019}=\frac{R}{2019}$，此时只需要在$[L \bmod 2019,R \bmod 2019]$中暴力求解就行。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
using namespace std;
typedef long long ll;
ll L,R;
int ans=9999;
int main(){
cin>>L>>R;
ll l1=L/2019;
ll l2=
ll r1=R/2019;
ll r2=
if(l2==0||r2==0||(r1-l1>=1)){
cout<<0;
return 0;
}
for(int i=l2;i<=r2;++i){
for(int j=i+1;j<=r2;++j){
ans=min(ans,(i*j
}
}
cout<<ans;
return 0;
}
D题
题目大意：有$n$座山围成一个环，每相邻两座山之间有一条沟渠。若有一座山的山上下了$2x$的雨，那么这座山相邻的两条沟渠分别可收集$x$的雨量。一开始每条沟渠蓄水量为$0$。现在把每条沟渠的蓄水量告诉你，求每一座山可能降下多少雨？
真·“水”题（划去）
其实这题蛮有意思的。比赛时我没想到列方程组，倒是想了个另外的方法——二分。
二分什么？二分第一座山的降雨量。之后按照顺时针或逆时针，每一座山的降雨量都可以推出来。之后最后一座山和第一座山之间的沟渠特判一下即可。
不过要注意什么时候返回true，什么时候返回false。因为根据奇偶性，不同的山降雨量大小对答案的影响不同。举个例子，若第一座山降雨量偏小。那么第二座山降雨量偏大。第三座山降雨量偏小，第四座山降雨量偏大......以此类推。可以用一个flag不断异或1来实现。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
using namespace std;
typedef long long ll;
int n;
ll a[400000];
int ans[400000];
int l,r;
inline int check(int x){
ans[1]=x*2;
int t=x,tmp;
bool flag=0;
for(int i=1;i<n;++i){
flag^=1;
tmp=a[i]-t;
if(tmp<0)return flag;
ans[i+1]=tmp*2;
t=tmp;
}
flag^=1;
tmp=a[n]-t-x;
if(tmp<0)return flag;
else if(tmp>0)return flag^1;
ans[n]=t*2;
return -1;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
l=0,r=2e9;
while(l<r){
int mid=(l+r)>>1;
int f=check(mid);
if(f==1)r=mid;
else if(f==0)l=mid+1;
else break;
}
for(int i=1;i<=n;++i)
printf(
return 0;
}
E题
题目大意：给一棵树，现在要在每个节点上染一种颜色（颜色种类为$1~K$），若两个点之间距离$\leq 2$，则这两个点的颜色不能相同。询问一共有多少种染色方法？答案对$1e9+7$取模。
这题稍微画一画就能发现规律的，本质上就是个计数原理。
你会发现：一个节点的亲儿子节点多少与亲儿子节点可以染色的种类有多少有关：比如第一个儿子可以染$p$种，那么第二个儿子可以染$p-1$种，第三个儿子可以染$p-2$种......
不过要注意根节点与其儿子节点之间的关系，与之后的计数不太一样(很小的差别)，这个在纸上画画亦可发现。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
using namespace std;
typedef long long ll;
int n,k;
const int N=100050;
const ll mod=1e9+7;
ll ans=1;
struct edge{
int v,nxt;
}e[N<<1];
int col[N];
int dep[N];
int head[N],ecnt;
ll a[N];
int f[N],son[N];
void ad(int u,int v){
e[++ecnt].v=v;
e[ecnt].nxt=head[u];
head[u]=ecnt;
}
void dfs1(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa)continue;
f[v]=u;
son[u]++;
dep[v]=dep[u]+1;
dfs1(v,u);
}
}
void dfs2(int u,int fa,ll val){
int t=son[u],nv=k;t--;
a[u]=val;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa)continue;
if(dep[v]<=1){
dfs2(v,u,--nv);
}
else{
dfs2(v,u,k-2-t);
t--;
}
}
}
int main(){
cin>>n>>k;
for(int i=1;i<n;++i){
int x,y;
cin>>x>>y;
ad(x,y),ad(y,x);
}
dfs1(1,0);
dfs2(1,0,k);
for(int i=1;i<=n;++i){
ans*=a[i];
an
}
printf(
return 0;
}
F题
题目大意：还是给你一棵$n$个节点树，每条边都有一个颜色和权值。颜色种类在$1~n-1$内。接下来$q$个询问，每次询问若将颜色为j的边的权值全部更改为$w$，问从节点$u$到节点$v$的权值和。询问之间互不影响。
这题比赛时没想出来。后来问了下群里的大佬们，不得
可以用离线算法：每个询问拆分成点到根节点的权值和，之后dfs一遍，每到一个节点就将该点的询问处理完。
在那之前要dfs一遍，记录根节点到该点的权值和以及经历了多少不同颜色的边等等。
代码先留空，后面再补。
Comments NOTHING