考场解题
T1 染色(color)：结论+构造
结论：\(1,2,3,4\) 循环节染色一定合法。
证明：
- 对于 \(j-i=\) 奇数质数：
因为：
\[\text{偶数+奇数=奇数}\\ \text{奇数+奇数=偶数} \]奇偶不同色，所以可以满足所有的奇数质数。
- 对于 \(j-i=\) 偶数质数 \(2\)：
必须设置不同色。
因此对于 \(n\leq 8\) 的情况大表，否则 \(1,2,3,4\) 循环即可。
Miku's Code
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
#define cout std::cout
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef long double llf;
const ff eps=1e-8;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef set<int> SI;
int Max(int x,int y) <% return x<y?y:x; %>
int Min(int x,int y) <% return x<y?x:y; %>
int Abs(int x) <% return x>0?x:-x; %>
#if ONLINE_JUDGE
char INPUT[1<<20],*p1=INPUT,*p2=INPUT;
#define getchar() (p1==p2 && (p2=(p1=INPUT)+fread(INPUT,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
il int read(){
char c=getchar();
int x=0,f=1;
while(c<48) <% if(c=='-')f=-1;c=getchar(); %>
while(c>47) x=(x*10)+(c^48),c=getchar();
return x*f;
}const int maxn=1e4+5;
int n;
int main(){
freopen("color.in","r",stdin);
#if ONLINE_JUDGE
freopen("color.out","w",stdout);
#endif
n=read();
if(n==1) { puts("1"),puts("1");return 0; }
else if(n==2) { puts("1"),puts("1 1");return 0; }
else if(n==3) { puts("2"),puts("1 2 2");return 0; }
else if(n==4) { puts("2"),puts("1 2 2 1");return 0; }
else if(n==5) { puts("3"),puts("1 2 2 3 1");return 0; }
else if(n==6) { puts("3"),puts("1 2 2 3 1 1");return 0; }
else if(n==7) { puts("3"),puts("1 2 2 3 3 4 1");return 0; }
else if(n==8) { puts("3"),puts("1 2 2 3 1 1 2 3");return 0;}
else{
puts("4");
int len=n/4;
n=n-len*4;
for(rg i=1;i<=len;++i) printf("1 2 3 4 ");
int tot=0;
for(rg i=1;i<=n;++i) ++tot,printf("%d ",tot);
}
return 0;
}
T2 序列(array)：思维题
题干概括：
有两个长度为 \(m\) 的序列 \(a,b\)，在 \(0\leq b_i\leq n\) 且 \(\sum_{i=1}^{m}\limits a_ib_i\leq D\) 的情况下，求：
\[\sum_{i=1}^{m}b_i+k\cdot \min_{i=1}^{m}b_i \]的最大值。
思路：
容易证明的是，在 \(a_i\leq a_{i+1}\) 的条件下，\(b_{i}\geq b_{i+1}\) 一定更优。
因此我们对整个 \(a\) 进行排序，枚举 \(b\) 序列前 \(i\) 个元素大小为 \(n\)，第 \(i+1\) 个元素大小为 \(x\)，第 \(i+2\) 到第 \(m\) 个元素大小为 \(y\)。（\(n\geq x\geq y\)）
对于每一个 \(i\)，答案就是 \(f(x)\)：
\[\begin{aligned} &f(x)=i\cdot n+x+y\cdot\left(k+n-\left(i+2\right)+1\right)\\ &y=\left\lfloor{\frac{D-n\sum_{j=1}^{n}\limits a_i-a_{i+1}\cdot x}{\sum_{j=i+2}^{n}\limits a_j}}\right\rfloor\\ &f(x)=i\cdot n+x+\left\lfloor{\frac{D-n\sum_{j=1}^{n}\limits a_i-a_{i+1}\cdot x}{\sum_{j=i+2}^{n}\limits a_j}}\right\rfloor\times (k+n-i-1) \end{aligned} \]于是我们把这个函数化简成：
\[\begin{aligned} &f(x)=x+Ay\\ &y=\left\lfloor{\frac{C-Bx}{S}}\right\rfloor\\ &f(x)=x+A\left\lfloor{\frac{C-Bx}{S}}\right\rfloor\\ &(A\geq 0,B\geq 0,C\geq 0,S\geq 0) \end{aligned} \]然后画出他们的函数图像，发现其为锯齿状：
为什么是锯齿状的？因为：
\[y=\left\lfloor{\frac{C-Bx}{S}}\right\rfloor \]\(y\) 是一个向下取整的函数，在 \(x\) 变化的一定区间内，\(y\) 不变，在 \(y\) 不变的区间内，\(x\) 增大，\(f(x)\) 一定增大。
由 \(y\geq 0\)，可以得到：
\[Sy+Bx\leq C \]而 \(x\) 有一个定义域，由 \(n\) 和 \(D\) 决定，在定义域内，答案有三种情况：
- 在第一个峰：
因为 \(y\leq x\)，所以我们可以先假设 \(x=y\)，求出最小的 \(y\)，然后将剩下的值 \(C-Sy\) 全部赋给 \(x\)。
// 1:保证x尽可能小，因为x>=y，假设x等于y之后填x
ll y=Min(C/(B+S),n),x=Min(C/(B+S)+C%(B+S)/B,n);
ans=Max(ans,n*i+x+A*y);
- 在 \(x\) 的最大值上：
直接求 \(x\) 的最大值，假设 \(y=0\) 即可。
// 2:保证x尽可能大，假设y=0
x=Min(C/B,n),y=0;
if(x>=y) ans=Max(ans,n*i+x+A*y);
- 在最后一个峰上：
由上不等式得到：\(x\) 越大，\(y\) 越小。
设在答案点上的 \(x=xx,y=yy\)，\(ans=xx+Ayy\)。
\[\begin{aligned} &y\leq \frac{C-Bxx}{S}\\ &yy=\left\lfloor{\frac{C-B xx}{S}}\right\rfloor\\ &Syy\leq C-Bxx\\ &Syy\geq C-Bn\\ &Syy> C-Bn-1\\ &yy>\left\lfloor{\frac{C-Bn-1}{S}}\right\rfloor\\ &yy=\left\lfloor{\frac{C-Bn-1}{S}}\right\rfloor+1\\ &xx\leq \frac{C-Syy}{B}\\ &xx=\left\lfloor{\frac{C-Syy}{B}}\right\rfloor \end{aligned} \]// 3:最后的峰点
if(C-B*n>1){
int y=(C-B*n)/S,x=(C-S*y)/B;
if(x>=y) ans=Max(ans,n*i+x+A*y);
}
时间复杂度：\(O(Tm)\)。
Miku's Code
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
#define cout std::cout
#define endl '\n'
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef long double llf;
const ff eps=1e-8;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef set<int> SI;
int Max(int x,int y) <% return x<y?y:x; %>
int Min(int x,int y) <% return x<y?x:y; %>
int Abs(int x) <% return x>0?x:-x; %>
#if ONLINE_JUDGE
char INPUT[1<<20],*p1=INPUT,*p2=INPUT;
#define getchar() (p1==p2 && (p2=(p1=INPUT)+fread(INPUT,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
il int read(){
char c=getchar();
int x=0,f=1;
while(c<48) <% if(c=='-')f=-1;c=getchar(); %>
while(c>47) x=(x*10)+(c^48),c=getchar();
return x*f;
}const int maxm=2e5+5;
int T;
int n,m,k,D,a[maxm],sum[maxm],ans;
il void clear(){
ans=0;
for(rg i=0;i<=m;++i) sum[i]=0;
}
il void input(){
n=read(),m=read(),k=read(),D=read();
for(rg i=1;i<=m;++i) a[i]=read();
}
signed main(){
freopen("array.in","r",stdin);
#if ONLINE_JUDGE
freopen("array.out","w",stdout);
#endif
T=read();
while(T--){
input();
sort(a+1,a+m+1);
for(rg i=1;i<=m;++i) sum[i]=sum[i-1]+a[i];
if(n*sum[m]<=D) { printf("%lld\n",n*(m+k));continue; }
for(rg i=0;i<m;++i){
if(n*sum[i]>D) break;
ll A=m-i-1+k,B=a[i+1],C=D-sum[i]*n,S=sum[m]-sum[i+1];
if(!S){ ans=Max(ans,i*n+Min(C/B,n)*(1+k));continue; }
else{
// 1:保证x尽可能小，因为x>=y，假设x等于y之后填x
ll y=Min(C/(B+S),n),x=Min(C/(B+S)+C%(B+S)/B,n);
ans=Max(ans,n*i+x+A*y);
// 2:保证x尽可能大，假设y=0
x=Min(C/B,n),y=0;
if(x>=y) ans=Max(ans,n*i+x+A*y);
// 3:最后的峰点
if(C-B*n>1){
int y=(C-B*n)/S,x=(C-S*y)/B;
if(x>=y) ans=Max(ans,n*i+x+A*y);
}
}
}
printf("%lld\n",ans);
clear();
}
return 0;
}
T3 树上询问(query)：树链剖分+树上查分
如题。
Miku's Code
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
#define cout std::cout
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef long double llf;
const ff eps=1e-8;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef set<int> SI;
int Max(int x,int y) <% return x<y?y:x; %>
int Min(int x,int y) <% return x<y?x:y; %>
int Abs(int x) <% return x>0?x:-x; %>
#if ONLINE_JUDGE
char INPUT[1<<20],*p1=INPUT,*p2=INPUT;
#define getchar() (p1==p2 && (p2=(p1=INPUT)+fread(INPUT,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
il int read(){
char c=getchar();
int x=0,f=1;
while(c<48) <% if(c=='-')f=-1;c=getchar(); %>
while(c>47) x=(x*10)+(c^48),c=getchar();
return x*f;
}const int maxn=3e5+5;
int n,m,ans[maxn];
int head[maxn<<1],t;
#define next Miku
struct edge{ int v;int next; };edge e[maxn<<1];
struct Node{
int id,opt,add,k;
Node(int idd,int optt,int addd,int kk): id(idd),opt(optt),add(addd),k(kk) {};
};
vector<Node> s[maxn];
il void add_edge(int u,int v){ e[++t].v=v;e[t].next=head[u];head[u]=t; }
namespace TreeChain{
int dep[maxn],myf[maxn],sonum[maxn],hson[maxn],top[maxn];
void dfs1(int now,int fa){
dep[now]=dep[fa]+1;
myf[now]=fa;
sonum[now]=1;
for(rg i=head[now];i;i=e[i].next){
int to=e[i].v;
if(to==fa) continue;
dfs1(to,now);
sonum[now]+=sonum[to];
if(sonum[hson[now]]<sonum[to]) hson[now]=to;
}
}
void dfs2(int now,int topp){
top[now]=topp;
if(!hson[now]) return;
dfs2(hson[now],topp);
for(rg i=head[now];i;i=e[i].next){
int to=e[i].v;
if(to!=myf[now] && to!=hson[now]) dfs2(to,to);
}
}
il int LCA(int x,int y){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy]) swap(fx,fy),swap(x,y);
x=myf[fx],fx=top[x];
}
return (dep[x]<dep[y])?x:y;
}
}using namespace TreeChain;
int save1[maxn*3],save2[maxn*3],base;
il void solve(int x){
++save1[x+dep[x]];++save2[dep[x]-x+base];
for(rg i=0;i<s[x].size();++i){
Node y=s[x].at(i);
// cerr<<"###"<<y.id<<' '<<y.k<<' '<<y.add<<endl;
if(y.add&1) ans[y.id]+=y.opt*save1[y.k];
else ans[y.id]+=y.opt*save2[y.k+base];
}
for(rg i=head[x];i;i=e[i].next){
int to=e[i].v;
if(to==myf[x]) continue;
solve(to);
}
--save1[x+dep[x]];--save2[dep[x]-x+base];
}
il void input(){
n=read();m=read();
int u,v;
for(rg i=1;i<=n-1;++i) u=read(),v=read(),add_edge(u,v),add_edge(v,u);
}
int main(){
freopen("query.in","r",stdin);
#if ONLINE_JUDGE
freopen("query.out","w",stdout);
#endif
input();
base=n+10;
dfs1(1,0);
dfs2(1,0);
int tim=0,l,r,sm=m;
while(m--){
++tim;
l=read(),r=read();
int lca=LCA(l,r);
int len=(dep[l]-dep[lca])+(dep[r]-dep[lca]);
s[l].push_back(Node(tim,1,1,dep[l]));
s[r].push_back(Node(tim,1,2,dep[r]-len));
s[lca].push_back(Node(tim,-1,1,dep[l]));
s[myf[lca]].push_back(Node(tim,-1,2,dep[r]-len));
}
solve(1);
for(rg i=1;i<=sm;++i) printf("%d\n",ans[i]);
return 0;
}
考场解题
考场解题
无大样例场。
T1 染色(color)
\(n\leq 10^4\)。
所以并不需要去想规律，想结论，想构造。
直接预处理所有质数，然后往前找。
最后找到可以放的数就可以了。
T2 序列(array)
手模样例发现，答案可以通过两次不同的寻找找到：
- 保证 \(\sum\) 尽可能大。
为了保障 \(\sum\) 尽可能大，我们将原数组 \(a\) 排序，对于最小的 \(a_1\) 我们让其搭配最大的 \(b_1\)，而后面的 \(a_2,a_3,\dots,a_n\) 我们搭配小的 \(b=1\)。
然后再此基础上，不断减小 \(b_1\) 使其合法。
- 保证 \(\min\) 尽可能大。
为了保证 \(\min\) 尽可能大，我们将原数组 \(a\) 求和，对于所有 \(a\) 我们都让其搭配相同的 \(b\)，在此基础上从前往后扫，给 \(a_1\)，\(a_2\) 等值 \(++b_1,b_2\)，使其合法。
可能假了，正确性不会证明。
前面的因为 linux 重启了所以丢了呜，所以凭借记忆复原了呜。
T3 树上询问(query)
先打个树链剖分暴力，然后再拿特殊性质。
非常好的过了样例。
发现特殊性质没什么可拿的，就算是一条链我的思路也是和我的暴力没什么区别。
T4 网络(network)
puts("NO") 了。
希望是不可以总司令题。