序列
一道没有除了分支和循环外任何算法的题 非常适合初学者
1.特殊解出答案 因为合法解都是转动“嵌套”出来的 但是这个结论需要考虑到倒序的方法才能想到
2.发现正序无法确定每个数的位置 但是倒过来用倒序放置每个已放置的数的位置就是固定的 形成一段前后缀
用 \(n\) 个序列一起构造一个特殊解
每次每个排列都放置一个数 每个排列放置的数的个数相等
考虑有几种情况（按优先级来）：
1.每个排列对应的前缀长度都相等 后缀长度都相等 那么我们可以直接把里外翻转 所以方案数乘2 前后缀随便放一个即可
2.这个数跟前后缀的下/上一位的位置对应的特殊解处的数一样 直接放
3.如果前后缀上/下一位有空位，放到空位上（因为前后缀上/下一位都有空位其实就是第一种情况，所以我们其实只有一种选择）
4.无解
然后考虑构造 按照贪心应该是先转外层 但是发现每一层都是独立的 顺序其实不影响 先转外层会影响里层区间范围 所以先转里层
Code
#include<iostream>
#define Sakura int
#define Re register ll
#define _ putchar(' ')
#define el putchar('\n')
#define ll long long
#define fre(x,y) freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);
using namespace std;
const ll maxn=1e3+10;
const ll mod=1e9+7;
inline ll read() {
ll x=0,f=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void ot(ll x) {
if(x<0) putchar('-'),x=-x;
if(x>9) ot(x/10);putchar(x%10|48);
}
ll T;
ll n,m;
ll a[maxn][maxn],b[maxn];
ll l[maxn],r[maxn];
ll L[maxn],R[maxn],tot;
ll ans;
inline ll qpow(ll x,ll d) {
ll res=1;
while(d){
if(d&1) res=res*x%mod;
x=x*x%mod;
d>>=1;
}
return res;
}
inline void reverse(ll id){
ll s=L[id]+R[id];
for(Re i=L[id];i<s-i;++i) swap(b[i],b[s-i]);
}
inline void solve() {
n=read(),m=read();
for(Re i=1;i<=n;++i)
for(Re j=1;j<=m;++j)
a[i][j]=read();
for(Re i=1;i<=n;++i) l[i]=1,r[i]=m;
for(Re i=1;i<=m;++i) b[i]=0;
L[1]=1,R[1]=m;
tot=1;
ans=0;
for(Re j=m;j>=1&&ans>=0;--j) {
for(Re i=1;i<=n;++i){
if(!b[l[i]]&&!b[r[i]]) {
ans+=l[i]!=r[i];
b[l[i]++]=a[i][j];
}
else if(b[l[i]]==a[i][j]) ++l[i];
else if(b[r[i]]==a[i][j]) --r[i];
else if(!b[r[i]]) b[r[i]--]=a[i][j];
else if(!b[l[i]]) b[l[i]++]=a[i][j];
else {
ans=-1;
break;
}
}
bool v=true;
for(Re i=2;i<=n&&v;++i) if(l[i]!=l[i-1]||r[i]!=r[i-1]) v=false;
if(v) L[++tot]=l[1],R[tot]=r[1];
}
ot(ans>=0?qpow(2,ans):0),el;
if(ans>=0) {
// for(Re i=1;i<=m;++i) ot(b[i]),_;el;
// for(Re i=1;i<=tot;++i) ot(L[i]),_,ot(R[i]),el;
for(Re i=tot;i>=1;--i)
if(i<tot&&R[i]==R[i+1]) {
if(b[L[i]]>b[L[i+1]]) reverse(i+1),reverse(i);
}
else if(L[i]<R[i]&&b[L[i]]>b[R[i]]) {
if(i<tot) reverse(i+1);
reverse(i);
}
for(Re i=1;i<=m;++i) ot(b[i]),_;el;
}
}
Sakura main(){
fre(array,array);
T=read();
while(T--) solve();
}
序列
是个细节贪心题
先把能选的所有点选上 然后逐个删点
删的话能删大的删大的 因为删了之后可以做边权
然后连一个编号小的父亲 同理
细节麻烦 直接贺的
Code
#include<iostream>
#include<set>
#define Sakura int
#define Re register ll
#define _ putchar(' ')
#define el putchar('\n')
#define ll long long
#define fre(x,y) freopen(#x".in","r",stdin),freopen(#y".out","w",stdout);
using namespace std;
const ll maxn=1e5+10;
inline ll read(){
ll x=0,f=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
inline void ot(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) ot(x/10);putchar(x%10|48);
}
multiset<ll> set1,set2;
ll n;
ll a[maxn],sum[maxn],b[maxn];
ll tot,limit;
ll fa[maxn];
ll ans[maxn];
bool vis[maxn];
Sakura main(){
fre(tree,tree);
n=read();
for(Re i=1;i<=n-1<<1;++i) ++a[read()];
for(Re i=1;i<=n;++i){
if(sum[i-1]<i-1) {
for(Re j=1;j<n;++j) ot(-1),_;
return 0;
}
sum[i]=sum[i-1]+a[i];
}
ll last=1;
for(Re i=2;i<=n;++i) {
if(sum[i-1]==i-1||i==n) vis[i]=true,++limit;
if(a[i]||i==n) fa[i]=last,--a[last],++tot,last=i;
}
// for(Re i=1;i<=n;++i) ot(fa[i]),ot(vis[i]),_;el;
ll u=1;
for(Re i=2;i<n;++i)
if(!fa[i]) {
while(!a[u]) ++u;
--a[u],fa[i]=u;
}
ll tmp=tot;
for(Re i=n-1;i;--i) {
ll x=min(tmp,a[i]);
ans[tot]+=x*i;
a[i]-=x;
b[i]+=x;
tmp-=x;
}
// for(Re i=1;i<=n;++i) ot(a[i]),_;el;
// for(Re i=1;i<=n;++i) ot(b[i]),_;el;
for(Re i=1;i<n;++i) {
for(Re j=1;j<=a[i];++j) set1.insert(i);
for(Re j=1;j<=b[i];++j) set2.insert(i);
}
// ot(tot),el;
// ot(limit),el;
// ot(ans[tot]),el;
--tot;
u=n;
while(tot>=limit) {
while(vis[fa[u]]) u=fa[u];
ll f=fa[u];
ans[tot]=ans[tot+1];
for(Re i=0;i<2;++i) {
ll x=*set2.begin();
set2.erase(set2.begin());
set1.insert(x);
ans[tot]-=x;
}
// ot(ans[tot]),el;
fa[u]=fa[f];
set1.insert(f);
ll x=*set1.begin();
set1.erase(set1.begin());
fa[f]=x;
x=*(--set1.end());
set1.erase(--set1.end());
set2.insert(x);
ans[tot]+=x;
--tot;
}
for(Re i=1;i<n;++i) ot(ans[i]?ans[i]:-1),_;
}
集合
6
标签：putchar,省选,ll,Re,maxn,联测,ans,define From： https://www.cnblogs.com/Sakura-Lu/p/17020386.html