这篇是比赛的题解部分。
题解的顺序按照自己认为的难易顺序排列。
本题直接输出即可，注意输出引号与反斜杠的格式。
本题是作者被儒略历坑惨之后用怨念口胡的题 （幻想乡历法与生辰八字的转化） 的极度简化版。
只要在一开始时按照周期六十预处理每个纪年所互相对应的结果后就可以对每个询问快速处理。
由于数据比较小，实际上你每一步都从已知的年份模拟下来也能过，std::map更可以。
当然你要解线性同余方程组得到解析解，我也不拦你（就是下面这篇）。（笑）
char sys[3][5][10]={{"hi","tsuki","hoshi"},//日月星
{"haru","natsu","aki","fuyu"},//春夏秋冬
{"tsuchi","ka","mizu","ki","kin"}};//土火水木金
char gz[2][12][10]={{"yi","bing","ding","wu","ji","geng","xin","ren","gui","jia"},//乙~甲
{"you","xu","hai","zi","chou","yin","mao","chen","si","wu","wei","shen"}};//酉~申
inline int toSys1(char s[])
{
if(s[0]==‘h‘ && s[1]==‘i‘) return 0;
if(s[0]==‘t‘) return 1;
if(s[0]==‘h‘ && s[1]==‘o‘) return 2;
}
inline int toSys2(char s[])
{
if(s[0]==‘h‘) return 0;
if(s[0]==‘n‘) return 1;
if(s[0]==‘a‘) return 2;
if(s[0]==‘f‘) return 3;
}
inline int toSys3(char s[])
{
if(s[0]==‘t‘) return 0;
if(s[0]==‘k‘ && s[1]==‘a‘) return 1;
if(s[0]==‘m‘) return 2;
if(s[0]==‘k‘ && s[2]==0) return 3;
if(s[0]==‘k‘ && s[2]==‘n‘) return 4;
}
inline int toGz1(char s[])
{
if(s[0]==‘y‘) return 0;
if(s[0]==‘b‘) return 1;
if(s[0]==‘d‘) return 2;
if(s[0]==‘w‘) return 3;
if(s[0]==‘j‘ && s[2]==0) return 4;
if(s[0]==‘g‘ && s[1]==‘e‘) return 5;
if(s[0]==‘x‘) return 6;
if(s[0]==‘r‘) return 7;
if(s[0]==‘g‘ && s[1]==‘u‘) return 8;
if(s[0]==‘j‘ && s[2]==‘a‘) return 9;
}
inline int toGz2(char s[])
{
if(s[0]==‘y‘ && s[1]==‘o‘) return 0;
if(s[0]==‘x‘) return 1;
if(s[0]==‘h‘) return 2;
if(s[0]==‘z‘) return 3;
if(s[0]==‘c‘ && s[2]==‘o‘) return 4;
if(s[0]==‘y‘ && s[1]==‘i‘) return 5;
if(s[0]==‘m‘) return 6;
if(s[0]==‘c‘ && s[2]==‘e‘) return 7;
if(s[0]==‘s‘ && s[1]==‘i‘) return 8;
if(s[0]==‘w‘ && s[1]==‘u‘) return 9;
if(s[0]==‘w‘ && s[1]==‘e‘) return 10;
if(s[0]==‘s‘ && s[1]==‘h‘) return 11;
}
inline void Solve()
{
#ifdef DEBUG
printf("Debuging...\n");
#endif
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int t;
scanf("%d",&t);
if(t==1)
{
char str1[10],str2[10],str3[10];
scanf("%s%s%s",str1,str2,str3);
int k=(40*toSys1(str1)+45*toSys2(str2)+36*toSys3(str3))%60;//todo
printf("%s %s\n",gz[0][k%10],gz[1][k%12]);
}
else
{
char str1[10],str2[10];
scanf("%s%s",str1,str2);
int k=(6*toGz1(str1)+55*toGz2(str2))%60;//todo
printf("%s %s %s\n",sys[0][k%3],sys[1][k%4],sys[2][k%5]);
}
}
return ;
}
首先，你需要将字符转化为高度，以便处理。
然后对于一个视图来说，某一列的高度的最大值决定了在这样一列的投影的高度。
所以，我们对于每一行（列）都求出这一（列）的高度最大值，就是侧（正）视图上的高度。
最后以纵向#的个数代表高度输出。
inline int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%s",g[i]+1);
for(int i=1;i<=k;i++)
{
scanf("%s%d",&t,&a);
sample[t[0]]=a;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
mx=Max(mx,sample[g[i][j]]);
fr[j]=Max(fr[j],sample[g[i][j]]);
si[i]=Max(si[i],sample[g[i][j]]);
}
printf("Front View\n");
for(int i=mx;i>=1;i--)
{
for(int j=1;j<=m;j++) putchar(fr[j]>=i?‘#‘:‘ ‘);
putchar(‘\n‘);
}
putchar(‘\n‘);
printf("Side View\n");
for(int i=mx;i>1;i--)
{
for(int j=1;j<=n;j++) putchar(si[j]>=i?‘#‘:‘ ‘);
putchar(‘\n‘);
}
for(int j=1;j<=n;j++) putchar(si[j]>=1?‘#‘:‘ ‘);//to avoid end empty line
return 0;
}
本题等价于求一个平均数最大的子矩阵。
因为对于一组数 \(a_i\) 一个数 \(p < \bar{a}_n\)，将 \(p\) 加入数列 \(a\) 后数列的平均值 \(\bar{a}_{n+1}=\frac{p+n* \bar{a}_n}{n+1}=\frac{(n+1)* \bar{a}_n+p-\bar{a}_n}{n+1}=\bar{a}_n+\frac{p-\bar{a}_n}{n+1}<\bar{a}_n\)。
所以我们知道，选入要选的矩阵中的数偏小，总共的平均值也会偏小，类似于被“冲淡”的作用。
所以我们只需要输出整个矩阵中元素的最大值即可。
我们容易知道，一个矩形是某个大矩形的子矩形，当且仅当大矩形的编码为小矩形编码的前缀。
所以我们可以对字符串前缀排序，如果后面的矩形编码有前面矩形的作为其前缀的时候，那么说明这个矩形被覆盖到了，不将它统计入答案，否则统计进答案。
因为已经经过前缀排序，所以大矩阵肯定在子矩阵前面。于是考虑顺序遍历排完序的字符串数组，存储一个可能作为前缀的编码。如果该编码以存储编码作为前缀，那么略过，否则计入答案，更新存储的编码（因为它可能作为后面某编码的前缀）。
int n;
double sa,ans;
const double all=(double)(1<<18);
struct NHash
{
int len;
char code[24];
}sc[N];
bool cmp1(NHash a,NHash b)//前缀排序
{
int len=min(a.len,b.len);
for(int i=0;i<len;i++) if(a.code[i]!=b.code[i]) return a.code[i]<b.code[i];
return a.len<b.len;
}
bool cmp2(NHash a,NHash b)//判断a是否不为b的前缀
{
//printf("cmp %s %s\n",a.code,b.code);
if(a.len>b.len) return true;
else
{
for(int i=0;i<a.len;i++)
{
//printf("\t%d %c %c\n",i,a.code[i],b.code[i]);
if(a.code[i]!=b.code[i])
return true;
}
}
return false;
}
inline void Solve()
{
#ifdef DEBUG
printf("Debuging...\n");
#endif
scanf("%d%lf",&n,&sa);
sa*=sa;
for(int i=1;i<=n;i++)
{
scanf("%s",sc[i].code);
sc[i].len=strlen(sc[i].code);
}
sort(sc+1,sc+n+1,cmp1);
//n=unique(sc+1,sc+n+1)-sc;
NHash now={0,""};
for(int i=1;i<=n;i++)
{
if(i==1 || cmp2(now,sc[i])) ans+=1ll<<(19-sc[i].len),now=sc[i];//,printf("add %d\n %s\n",sc[i].len-1,sc[i].code)
}
//printf("%f\n",ans);
printf("%.3f\n",ans/all*sa);
return ;
}
因为和前缀有关系，所以你写一颗Trie然后遍历也是对的。
但是由于个人对题目复杂度情况的疏忽，导致了二维差分与直接以编码为Hash值查重的解法也能够通过本题。
现在出题人很后悔（
我们对代码文本进行编辑，只允许删除和添加，那么所求最小值与最长公共子序列有关，第一个代码段中未出现最长公共子序列部分即被删除，第二个代码段中未出现最长公共子序列部分即为添加部分。
最长公共子序列是指两个字符串里面连续不一定相邻的最长的公共字符，
假设我们用\(dp[i,j]\)表示 A 和 B 的LCS的长度（直接保存最长公共子序列的中间结果不现实，需要先借助LCS的长度），那么存在以下递推式
int n;
cin>>n;
cin.get();
for(int i=0;i<n;i++)getline(cin,s1[i]);
int m;
cin>>m;
cin.get();
for(int i=0;i<m;i++)getline(cin,s2[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<n+m-dp[n][m]*2<<"\n";
通过对小数据的观察分析发现，我们只需要构造图的一棵生成树。先从最底下的边开始把便士放到底部的叶子节点上（从它的父节点移动到该节点），如果某个节点已经只有一个空点与其相连，那么它也就成为了“叶子节点”进入决策范围中。不断重复这个过程，直到只剩下根节点作为空节点。
整个过程可以用dfs实现。
void dfs(int x)
{
vi[x]=1;
for(int i=H[x];i;i=K[i])
{
int y=V[i];
if(vi[y]) continue;
fm[++cnt]=x,to[cnt]=y;
dfs(y);
}
}
//...
dfs(1);
if(cnt!=n-1) return printf("Impossible!\n");
else
{
for(int i=cnt;i>=1;--i)
printf("%d -> %d\n",fm[i],to[i]);
}
本题相当于在一个有正边权和整数点权的DAG上找到一条路径和该路径上的一些点，使得总权值最小。直接Topo Sort后在DAG上进行dp即可。
//c: 单个站点的净收益
//q：topo sort的队列
inline ll Topo()
{
d[s]=0;
head=1,tail=0;
for(int x=1;x<=n;x++)
if(!deg[x]) q[++tail]=x;
for(;head<=tail;)
{
int x=q[head++];
vi[x]=1;
if(x==t) return d[x]+c[x];
d[x]+=c[x];
for(int i=H[x];i;i=K[i])
{
int y=V[i];
if(vi[y]) continue;
--deg[y];
if(!deg[y]) q[++tail]=y;
d[y]=min(d[y],d[x]+E[i]);
}
}
return 114514;
}
inline void Solve()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",c+i);
for(int i=1;i<=n;i++){int p; scanf("%d",&p); c[i]-=p;}
for(int i=1;i<=m;i++)
{
int u,v,w; scanf("%d%d%d",&u,&v,&w);
Add(u,v,w),++deg[v];
}
scanf("%d%d",&s,&t);
//for(int i=1;i<=n;i++) printf("%d ",c[i]); putchar(‘\n‘);
for(int i=1;i<=n;i++) if(i!=s && i!=t) c[i]=min(c[i],0);
//for(int i=1;i<=n;i++) printf("%d ",c[i]); putchar(‘\n‘);
memset(d,0x3f,sizeof(d));
printf("%lld\n",Topo());
//for(int i=1;i<=n;i++) printf("%d-%lld\n",i,d[i]);
return ;
}
由高中数学知识可以知道，一个大小为 \(k\) 的可重集 \(S\) 的全部子集的元素和之和应该等于 \(2^{k-1} \sum{S_i}\)（证明的话考虑每个元素出现在那几个子集里即可）。集合的合并考虑用并查集维护，注意合并时应维护集合的大小与元素之和。
//并查集
int fa[N],rnk[N];
ll sum[N];
inline void init(){for(int i=1;i<=n;i++) fa[i]=i,rnk[i]=1;}
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
inline void Union(int x,int y)
{
x=Find(x),y=Find(y);
if(x==y) return;
if(rnk[x]<rnk[y]) swap(x,y);
fa[y]=x,rnk[x]+=rnk[y],sum[x]=(sum[x]+sum[y])%p;
}
//in every query
int op=read();
if(op==1)
{
int x=read(),y=read();
Union(x,y);
}
else if(op==2)
{
int x=read(),k=read(); x=Find(x);
sum[x]=(sum[x]+p+k)%p;
}
else
{
int x=read(); x=Find(x);
printf("%lld\n",(qpower(2,rnk[x]-1)*sum[x])%p);
}
设字符串长度为 \(n\)。
暴力修改（一堆人这么做），复杂度 \(O(nm)\)，可以获得Wrong Answer的好成绩。
本题相当于区间推平单点查询操作（一开始区间修改，最后 \(n\) 次单点查询）。考虑用线段树维护，区间修改区间内的字符格式，查询每个字符。复杂度 \(O((n+m)\log n)\)
inline void push(int rt)
{
caps[rt]=max(caps[rt<<1],caps[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(l==r)
{
if(s[l]>=‘A‘&&s[l]<=‘Z‘)
{
caps[rt]=2;
s[l]+=32;
}
else caps[rt]=1;
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
push(rt);
}
inline void pushdown(int rt,int len)
{
if(!add[rt]) return;
add[rt<<1]=add[rt];
add[rt<<1|1]=add[rt];
caps[rt<<1]=add[rt];
caps[rt<<1|1]=add[rt];
add[rt]=0;
}
void modify(int L,int R,int v,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
add[rt]=v;
caps[rt]=v;
return;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid) modify(L,R,v,lson);
if(R>mid) modify(L,R,v,rson);
push(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return caps[rt];
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
int ans=-INF;
if(L<=mid) ans=max(ans,query(L,R,lson));
if(R>mid) ans=max(ans,query(L,R,rson));
return ans;
}
int main()
{
//freopen("data16.in","r",stdin);
//freopen("data16!.out","w",stdout);
int fm,a,b;
scanf("%d",&m);
scanf("%*c%*c%[^\n]",s+1);
//Test:printf("%s",s+1);
n=strlen(s+1);
if((s[1]>=‘A‘&&s[1]<=‘Z‘)||(s[1]>=‘a‘&&s[1]<=‘z‘)) fir[1]=1;
for(register int i=1;i<=n;i++)
if(s[i-1]==‘ ‘&&((s[i]>=‘A‘&&s[i]<=‘Z‘)||(s[i]>=‘a‘&&s[i]<=‘z‘)))
fir[i]=1;
build(1,n,1);
while(m--)
{
fm=Read();a=Read();b=Read();
modify(a,b,fm,1,n,1);
}
for(register int i=1;i<=n;i++)
{
switch(query(i,i,1,n,1))
{
case 1:putchar(s[i]);break;
case 2:putchar(s[i]==32?32:s[i]-32);break;
case 3:putchar(fir[i]?(s[i]-32):s[i]);
}
}
return 0;
}
因为到了最后才输出结果，所以考虑离线算法.因为区间推平的覆盖性，所以每一个点都只考虑最后一次修改，对修改指令倒序处理。然后考虑在线段树中，每个节点保存一个是否修改过的tag。pushup时就看两个子节点是否修改过，然后之后只修改从未修改过的节点。
因为这种做法排除了重复修改的冗余操作，最后复杂度等价于n次线段树单点修改，即 \(O(n\log n)\)。
inline void toup(char& ch){if(‘a‘<=ch&&ch<=‘z‘) ch-=32;}
inline void tolow(char& ch){if(‘A‘<=ch&&ch<=‘Z‘) ch+=32;}
struct SegmentTree
{
int l,r;
int c;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define c(x) tree[x].c
}tree[4*N];
#define lc (p<<1)
#define rc (p<<1|1)
void build(int p,int l,int r)
{
l(p)=l,r(p)=r;
if(l==r) return;
int mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
}
inline void modify(int k,int q)
{
if(q==1) tolow(str[k]);
if(q==2) toup(str[k]);
if(q==3) tag[k]?toup(str[k]):tolow(str[k]);
}
void update(int p,int q,int l,int r)
{
if(l(p)==r(p)){modify(l(p),q); c(p)=1; return;}
int mid=(l(p)+r(p))/2;
if(l<=mid && !c(lc)) update(lc,q,l,r);
if(mid<r && !c(rc)) update(rc,q,l,r);
c(p)=c(lc)&c(rc);
}
inline void Solve()
{
#ifdef DEBUG
printf("Debuging...\n");
#endif
scanf("%d",&m); cin.getline(tmp,10);
tag[1]=1;
for(char ch=getchar();ch!=‘\n‘;ch=getchar())
{
str[++len]=ch;
if(ch==‘ ‘) tag[len+1]=1;
}
//printf("%d\n",len);
//printf("%s\n",str+1);
for(int i=m;i>=1;--i)
q[i]=read(),l[i]=read(),r[i]=read();
build(1,1,len);
for(int i=1;i<=m;++i)
update(1,q[i],l[i],r[i]); //printf("%d %d %d %d\n",i,q[i],l[i],r[i]),
printf("%s\n",str+1);
return ;
}
inline void dfs(int u,int fa){
vis[u]=1;
priority_queue<int,vector<int>,less<int> > q;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fa) continue;
dfs(v,u);
if(a[v]) q.push(a[v]);
}
while(a[u]&&(!q.empty())){
int x=q.top();q.pop();
if(q.empty()){
q.push(x);
break;
}
else{
int y=q.top();q.pop();
x--;y--;a[u]--;ans--;
if(x) q.push(x);
if(y) q.push(y);
}
}
if(a[u]&&(!q.empty())){
int x=q.top();q.pop();
if(a[u]>x){
ans+=a[u]-x;
}
}
else if(a[u]&&q.empty()){
ans+=a[u];
}
}
//ans即为所求答案
for(int i=1;i<=n;i++){
if(!vis[i]) dfs(i,i);
}
printf("%d\n",ans);
原文：https://www.cnblogs.com/lsCoinred/p/TZHSPC2021-di-ka.html