考的有一点意外，出乎意料。
[CF1060E] Sergey and Subway
考场上打假了，乐。
设 \(dis_{i,j}\) 表示 \(i\) 和 \(j\) 的树上距离。
很容易发现，答案其实就是：
\[\sum \lceil \frac{dis_{i,j}}{2} \rceil \]其实就是所有点对的距离，加上距离为奇数的点对的个数，最后除以二就可以了。
复杂度 \(O(n)\)
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
const int MAXN=2e5+10;
using namespace std;
inline int read() {
int f=1,x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') {
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
int n,cnt,ans,tot,s0,s1;
int dep[MAXN],siz[MAXN],fa[MAXN];
struct edge {
int to,next;
}a[MAXN<<1];
int head[MAXN];
void add(int u,int v) {
a[++cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
int g(int x) {
if(x&1) return (x+1)/2;
return x/2;
}
void dfs(int now,int father) {
dep[now]=dep[father]+1;
siz[now]=1;
if(dep[now]&1) s1++;
else s0++;
for(int i=head[now];i;i=a[i].next) {
int v=a[i].to;
if(v==father) continue;
dfs(v,now);
siz[now]+=siz[v];
}
}
void dfs1(int now,int father) {
for(int i=head[now];i;i=a[i].next) {
int v=a[i].to;
if(v==father) continue;
tot+=(siz[v]*(n-siz[v]));
dfs1(v,now);
}
}
signed main() {
n=read();
for(int i=1;i<n;i++) {
int u=read(),v=read();
add(u,v);
add(v,u);
}
dfs(1,0);
int sum=0;
for(int i=1;i<=n;i++) {
if(dep[i]&1) {
sum+=s0;
}
else {
sum+=s1;
}
}
sum/=2;
dfs1(1,0);
printf("%lld",(tot+sum)/2);
return 0;
}
/*
4
1 2
1 3
1 4
*/
[CF979D] Kuro and GCD and XOR and SUM
可以先考虑暴力，拿下10分。
观察数据范围，发现值域比较的小。
先考虑第二个条件，$ k|\gcd(v,x) $ ,在这里其实就是 \(k|v\) 且 \(k|x\) 的意思，
考虑第三个条件，异或最大值经典做法是 01-tire ,这里只不过加了几个限制。
对于第二个限制，我们可以在加入元素时，根据元素的约数（可以预处理出来）各建一个 Tire ,在每个约数的 Tire 内插入这个元素，查询 \(k\) 时直接在 \(k\) 的那个 Tire 里找就可以。
对于第一个限制，我们考虑对于 Trie 的每个节点设一个 \(mi\) 值，表示的是经过这个节点的数的最小值，如果 \(mi<k\) ,就不可以往这里走，换另一边。
复杂度 ，时间复杂度为 \(O(x\log{x})\) ,空间复杂度为 \(O(x\log{x})\)
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define int long long
const int MAXN=1e7;
const int M=1e5+10;
const int inf=1e18;
using namespace std;
inline int read() {
int f=1,x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') {
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
int q,cnt;
struct Tire {
int son[2];
}tr[MAXN];
int mi[MAXN],rt[M];
bool vis[M],a[M];
vector <int> y[MAXN];
void init() {
for(int i=1;i<=1e5;i++) {
for(int j=i;j<=1e5;j+=i) {
y[j].push_back(i);
}
}
}
void insert(int root,int x) {
int now=root;
mi[root]=min(mi[root],x);
for(int i=31;i>=0;i--) {
int ch=((x>>i)&1);
if(!tr[now].son[ch]) {
tr[now].son[ch]=++cnt;
}
now=tr[now].son[ch];
mi[now]=min(mi[now],x);
}
}
int query(int k,int x,int s) {
int now=rt[k];
if(x%k!=0 || mi[now]+x>s) {
return -1;
}
int ans=0;
for(int i=31;i>=0;i--) {
int ch=((x>>i)&1);
if(tr[now].son[!ch] && mi[tr[now].son[!ch]]+x<=s) {
ans+=((ch^1)<<i);
now=tr[now].son[!ch];
}
else {
ans+=(ch<<i);
now=tr[now].son[ch];
}
}
return ans;
}
signed main() {
init();
for(int i=0;i<=1e7;i++) {
mi[i]=inf;
}
q=read();
for(int g=1;g<=q;g++) {
int op=read();
if(op==1) {
int x=read();
if(a[x]) continue;
a[x]=1;
for(int i=0;i<y[x].size();i++) {
int now=y[x][i];
if(!vis[now]) {
rt[now]=++cnt;
vis[now]=1;
}
insert(rt[now],x);
}
}
if(op==2) {
int x=read(),k=read(),s=read();
printf("%lld\n",query(k,x,s));
}
}
return 0;
}
/*
5
1 1
1 2
2 1 1 3
2 1 1 2
2 1 1 1
*/
/*
2
1
-1
*/
[CF1101F] Trucks and Cities
直接暴力二分，再加上一些神奇的优化，就可以跑的飞快，非常的nice,在OJ上拿下最优解 （但不是正解）
点击查看代码
#include <iostream>
#include <cstdio>
#define int long long
const int MAXN=410;
const int inf=2e18;
using namespace std;
inline int read() {
int f=1,x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') {
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
int n,m,s,t,c,r,ans;
int a[MAXN];
bool check(int x) {
int rr=r,now=x;
bool flag=1;
for(int i=s;i<t;i++) {
int sp=(a[i+1]-a[i])*c;
if(sp>now) {
if(rr==0) return 0;
now=x;
rr--;
if(now<sp) {
return 0;
}
}
now-=sp;
}
return 1;
}
signed main() {
//freopen("drive.in","r",stdin);
// freopen("drive.out","w",stdout);
n=read() ,m=read();
for(int i=1;i<=n;i++) {
a[i]=read();
}
for(int i=1;i<=m;i++) {
s=read() ,t=read() ,c=read() ,r=read();
int z=ans,y=inf,sum=0;
if(check(ans)) continue;
while(z<=y) {
int mid=(z+y)>>1;
if(check(mid)) {
sum=mid;
y=mid-1;
}
else {
z=mid+1;
}
}
ans=max(sum,ans);
}
printf("%lld\n",ans);
return 0;
}
/*
7 6
2 5 7 10 14 15 17
1 3 10 0
1 7 12 7
4 5 13 3
4 7 10 1
4 7 10 1
1 5 11 2
*/