70+100+0=170。结论题自己还是要多试几组小数据。这套题还不错。
ZYB之国是特殊的六边形构造。
已知王国一共有??户家庭，每个家庭需占据一个不同的六边形格子。
王国里交流很频繁，所以这些家庭要构成一个连通区域；同时出于安全考虑，国王ZYB想在外面“围”一圈墙。
围墙需要遵守这样的规则：
定义围墙的长度为它占据的格子的数量。
请你帮国王ZYB安排每户家庭的具体位置以及围墙的建造方案，使得围墙的长度最短。
100% ：1 ≤ ?? ≤ 109
猜结论：最优建造方案一定是从里向外绕圈，最后在外面围一圈围墙。
然后找规律就行了。
首先若完整的绕了 \(i\) 圈，那么其中一共有 \(6\frac{i(i-1)}{2}+1\) 个格子，更外面一层的边长是 \(i\)。解出满足 \(6\frac{i(i-1)}{2}+1\leq n\) 的最大的 \(i\)，然后算出余下的格子占了附加的 \(j~(j<6)\) 条边和 \(k~(k<i)\) 个格子。
然后修墙一定是先把 \(i+1\) 圈补满然后再把开放部分围一圈。那么
\[
ans=\begin{cases}
(6-j-1)i+(j+1)(i+1) & k>0\(6-j)i+j*(i+1)+[j>0] & k=0
\end{cases}
\]
暴力枚举来求解 \(i\)，时间复杂度 \(O(\sqrt{n})\)。
int main(){
freopen("wall.in","r",stdin),freopen("wall.out","w",stdout);
int n=read<int>();
int i=1;
while(3*i*(i-1)+1<=n) ++i;
--i;
int m=n-(3*i*(i-1)+1);
int j=m/i,k=m%i;
// cerr<<"j="<<j<<" k="<<k<<endl;
int ans=k>0?(6-j-1)*i:(6-j)*i;
ans+=k>0?(j+1)*(i+1):j*(i+1)+(j>0); // edit 1: 1 -> (j>0)
printf("%d\n",ans);
return 0;
}这题出题人很良心地给了一张大网格，可以自己操作。
可爱的ZYB来到一个售货机前。
售货机里有一共有??(≤ 105) 个物品，每个物品有???? 个。自然，还有??个购买按钮。正常情况下，按下第?? 个按钮，需要支付???? 的钱，然后会跳出一份物品??。如果该物品卖完了，按下此按钮无效。
但是，这台售货机的电路连接出了点问题。第?? 个按钮的“弹出电路”连向了物品????。
假设按下了第?? 个按钮，售货机会按以下逻辑执行：
判断第?? 个物品是否为空。
如果是，不执行任何操作，退出该购买程序。
否则，要求支付???? 的钱。
因为电路坏了，实际弹出的物品会是????。
注意：如果物品???? 为空，显然也不会有物品弹出。
ZYB很快发现了售货机的秘密，并精确掌握了???? 的值。他又去调查了每一种物品的市场价。即他可以以???? 的价格卖掉物品??。
现在ZYB他想通过这台售货机，赚尽量多的钱。
假设ZYB有足够多的成本钱。
100% ：1 ≤ ?? ≤ 105
显然若 \(i\) 非空便可以对 \(f_i\) 进行扫货。若这样做有利可图的话，连一条从 \(f_i\) 到 \(i\) 价值为 \(D_{f_i}-C_i\) 的边。那么最终建出来的图是基环树森林。对每个树分别求最优解相加即可。
若一棵树没有环，那么对每个点找到它连出去的边的边权的最大值，从根到叶子扫货即可。
显然环需要特殊考虑的情况是这个环上的点每个点的最优决策对应的边都在环上。那么先把环上的点的存货卖到只剩一个，然后让某个点做出牺牲，用子树里的最大值来替换。找到这样做损失最小的点即可。
注意自环的情况，即若环大小为 \(1\)，那么就没有损失。
时间复杂度 \(O(n)\)。
co int N=100000+10;
int f[N],C[N],D[N],A[N];
vector<int> to[N],we[N];
int indeg[N],vis[N];
vector<int> re[N];
int outdeg[N];
deque<int> Q;
il void add_edge(int x,int y,int w){
// cerr<<"add "<<x<<" "<<y<<" "<<w<<endl;
to[x].push_back(y),we[x].push_back(w),++indeg[y];
re[y].push_back(x),++outdeg[x];
}
int cir[N],len;
void circle(int x){
vis[x]=1,cir[++len]=x;
for(int i=0;i<(int)to[x].size();++i){
int y=to[x][i];
if(outdeg[y] and !vis[y]) {circle(y);break;}
}
}
pair<int,int> fir[N],sec[N];
LL solve(){
// cerr<<"len="<<len<<" cir=";
// for(int i=1;i<=len;++i) cerr<<" "<<cir[i];
// cerr<<endl;
bool flag=1;
int minw=1e9;
for(int i=1;i<=len;++i){
int x=cir[i];
for(int j=0;j<(int)to[x].size();++j){
int y=to[x][j];
pair<int,int> cho=make_pair(we[x][j],!outdeg[y]);
if(cho>sec[x]){
sec[x]=cho;
if(sec[x]>fir[x]) swap(sec[x],fir[x]);
}
}
minw=min(minw,fir[x].first-sec[x].first);
if(fir[x].second==1) flag=0;
}
LL ans=0;
for(int i=1;i<=len;++i){
int x=cir[i];
ans+=(LL)A[x]*fir[x].first;
for(int j=0;j<(int)to[x].size();++j){
int y=to[x][j];
if(!outdeg[y]) Q.push_back(y);
}
}
if(len>1 and flag) ans-=minw;
while(Q.size()){
int x=Q.front();
vis[x]=1,Q.pop_front();
int maxw=0;
for(int i=0;i<(int)to[x].size();++i) maxw=max(maxw,we[x][i]);
ans+=(LL)A[x]*maxw;
for(int i=0;i<(int)to[x].size();++i) Q.push_back(to[x][i]);
}
return ans;
}
int main(){
freopen("goods.in","r",stdin),freopen("goods.out","w",stdout);
int n=read<int>();
for(int i=1;i<=n;++i) read(f[i]),read(C[i]),read(D[i]),read(A[i]);
for(int i=1;i<=n;++i)if(D[f[i]]-C[i]>0) add_edge(f[i],i,D[f[i]]-C[i]);
LL ans=0;
for(int i=1;i<=n;++i)if(!indeg[i]) Q.push_back(i);
while(Q.size()){
int x=Q.front();
vis[x]=1,Q.pop_front();
int maxw=0;
for(int i=0;i<(int)to[x].size();++i) maxw=max(maxw,we[x][i]);
ans+=(LL)A[x]*maxw;
for(int i=0;i<(int)to[x].size();++i) Q.push_back(to[x][i]);
}
for(int i=1;i<=n;++i)if(!vis[i] and !outdeg[i]) Q.push_back(i);
while(Q.size()){
int x=Q.front();Q.pop_front();
for(int i=0;i<(int)re[x].size();++i){
int y=re[x][i];
if(--outdeg[y]==0) Q.push_back(y);
}
}
for(int i=1;i<=n;++i)if(!vis[i] and outdeg[i]){
len=0,circle(i);
ans+=solve();
}
printf("%lld\n",ans);
return 0;
}话说这题我差点就爆0了，要不是交之前看了一眼发现fir[x]写成了fir[i]。
ZYB获得了一个神秘的非空字符串??。
初始时，串??是空的。
ZYB会执行若干次这样的操作：
但是ZYB不小心把??弄丢了。
他告诉你现在的??是什么，请帮他还原出可能的??。
如果有多个??符合要求，选取长度最短的。
如果仍然有多解，选取字典序最小的。
100% ：|??| ≤ 200, ?? ≤ 10, ∑?|??| ≤ 666
这种套路是第一次见？或者我做过这样的题但是忘了。
co int N=200+10;
char a[N],b[N];
int n,all[26],app[26],rest[26];
tr1::unordered_set<string> S;
int f[N][N];
bool check(int len){
for(int i=1;i<=n;++i)
f[i][i-1]=1,f[i][i]=a[i]==b[1];
for(int l=2;l<=n;++l){
char c=b[(l-1)%len+1];
for(int i=1;i<=n-l+1;++i){
int j=i+l-1;
f[i][j]=f[i][j-1]&(a[j]==c);
for(int k=1;!f[i][j] and k*len<=l;++k)
f[i][j]|=f[i][j-k*len]&f[j-k*len+1][j];
}
}
return f[1][n];
}
void real_main(){
scanf("%s",a+1),n=strlen(a+1);
fill(all,all+26,0);
for(int i=1;i<=n;++i) ++all[a[i]-'a'];
S.clear();
string best;
for(int len=1;len<=n;++len)if(n%len==0){
copy(all,all+26,app);
int num=n/len;
bool flag=1;
for(int c=0;c<26;++c){
if(app[c]%num) {flag=0;break;}
app[c]/=num;
}
if(!flag) continue;
int found=0;
for(int i=1;i<=n-len+1;++i){
copy(app,app+26,rest);
bool valid=1;
for(int j=0;j<len;++j){
b[1+j]=a[i+j];
if(--rest[b[1+j]-'a']<0) {valid=0;break;}
}
if(!valid) continue;
b[1+len]=0;
string cur=b+1;
if(S.count(cur)) continue;
S.insert(cur);
if(check(len)){
if(!found) best=cur,found=1;
else best=min(best,cur);
}
}
if(found) break;
}
cout<<best<<endl;
}
int main(){
freopen("string.in","r",stdin),freopen("string.out","w",stdout);
for(int T=read<int>();T--;) real_main();
return 0;
}原文：https://www.cnblogs.com/autoint/p/test20190926.html