#4
[COCI2012-2013#2] INFORMACIJE
题面
因为是排列,所以一个位置和一个值是一一对应的,容易想到匹配上,我们只需要考虑如何建边即可。先每个位置向每个值连边,然后再删掉不合法的边。注意题意,是最大值或最小值为 \(x\),所以权值 \(x\) 的位置必然在 \([l,r]\) 内,删掉 \([1,l-1]\) 和 \([r+1,n]\) 向 \(x\) 连的边。对于 \([l,r]\) 内的点,如果限制最大值,则 \([l,r]\) 内的位置的权值不能大于 \(x\),删掉 \([l,r]\) 向 \([x+1,n]\) 连的边,如果限制最小值,则删去 \([l,r]\) 向 \([1,x-1]\) 连的边。最后跑匈牙利即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=410;
int n,m,head[N],ad[N][N],tot=1,couple[N],vis[N];
struct edge{
int v,nxt;
}e[N*N];
void add(int u,int v){
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
int find(int u){
if(vis[u]){
return 0;
}
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!couple[v]||find(couple[v])){
couple[v]=u;
couple[u]=v;
return 1;
}
}
return 0;
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ad[i][j]=1;
}
}
for(int i=1;i<=m;i++){
int opt,l,r,val;
read(opt),read(l),read(r),read(val);
if(opt==1){
for(int j=l;j<=r;j++){
for(int k=val+1;k<=n;k++){
ad[j][k]=0;
}
}
for(int j=1;j<l;j++){
ad[j][min(val,n+1)]=0;
}
for(int j=r+1;j<=n;j++){
ad[j][min(val,n+1)]=0;
}
}
else{
for(int j=l;j<=r;j++){
for(int k=1;k<min(n+1,val);k++){
ad[j][k]=0;
}
}
for(int j=1;j<l;j++){
ad[j][min(val,n+1)]=0;
}
for(int j=r+1;j<=n;j++){
ad[j][min(val,n+1)]=0;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ad[i][j]){
add(i,j+n);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
vis[j]=0;
}
if(!find(i)){
puts("-1");
return;
}
}
for(int i=1;i<=n;i++){
write_space(couple[i]-n);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[NOI2015] 品酒大会
题面
SA经典题,将LCP大于等于 \(r\) 的和转化为倒序处理,每次只处理LCP等于 \(r\) 的情况,再做一个后缀和。根据性质可以知道 \(LCP(i,j)=\min\limits_{p=\min(rk_i,rk_j)}^{\max(rk_i,rk_j)}ht_p\),维护若干个集合,每个集合中的任意两个后缀的LCP都大于等于当前处理的 \(ht_i\)。新添的 \(ht_i\) 会将 \(sa_i\) 和 \(sa_{i-1}\) 所在的集合合并,用并查集维护,每个集合记录一下大小,最大值,最小值即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10,inf=1e18;
char s[N];
int n,sa[N],ht[N],rk[N],ork[N<<2],buc[N],id[N],pid[N],a[N];
bool cmp(int x,int y,int w){
return ork[x]==ork[y]&&ork[x+w]==ork[y+w];
}
void build(){
int m=(1<<7),p=0;
for(int i=1;i<=n;i++){
rk[i]=s[i];
buc[rk[i]]++;
}
for(int i=1;i<=m;i++){
buc[i]=buc[i-1]+buc[i];
}
for(int i=n;i;i--){
sa[buc[rk[i]]--]=i;
}
for(int w=1;;w<<=1,m=p,p=0){
for(int i=n;i>n-w;i--){
id[++p]=i;
}
for(int i=1;i<=n;i++){
if(sa[i]>w){
id[++p]=sa[i]-w;
}
}
for(int i=0;i<=m;i++){
buc[i]=0;
}
for(int i=1;i<=n;i++){
pid[i]=rk[id[i]];
buc[pid[i]]++;
}
for(int i=1;i<=m;i++){
buc[i]=buc[i-1]+buc[i];
}
for(int i=n;i;i--){
sa[buc[pid[i]]--]=id[i];
}
for(int i=0;i<=n;i++){
ork[i]=rk[i];
}
p=0;
for(int i=1;i<=n;i++){
rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
if(p==n){
break;
}
}
for(int i=1,k=0;i<=n;i++){
if(k){
k--;
}
while(s[i+k]==s[sa[rk[i]-1]+k]){
k++;
}
ht[rk[i]]=k;
}
}
int sum,mx=-inf,ans_sum[N],ans_mx[N];
vector<int>q[N];
namespace dsu{
int fa[N],siz[N],mx[N],mn[N];
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
mx[i]=mn[i]=a[sa[i]];
q[ht[i]].pb(i);
}
}
int getfa(int u){
if(fa[u]!=u){
fa[u]=getfa(fa[u]);
}
return fa[u];
}
void merge(int u,int v){
u=getfa(u),v=getfa(v);
::sum+=siz[u]*siz[v];
::mx=max(::mx,max(mx[u]*mx[v],mn[u]*mn[v]));
fa[v]=u;
siz[u]+=siz[v];
mx[u]=max(mx[u],mx[v]);
mn[u]=min(mn[u],mn[v]);
}
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
s[i]=getchar();
while(s[i]<'a'||s[i]>'z'){
s[i]=getchar();
}
}
for(int i=1;i<=n;i++){
read(a[i]);
}
build();
dsu::init();
for(int i=n-1;i>=0;i--){
for(int j=0;j<q[i].size();j++){
dsu::merge(q[i][j],q[i][j]-1);
ans_sum[i]=sum;
ans_mx[i]=mx;
}
}
for(int i=0;i<n;i++){
write_space(ans_sum[i]);
write_endl(ans_mx[i]);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[ARC140D] One to One
题面
\(n\) 个点 \(n\) 条边,可以得到的是这必然是一个基环树森林,为了方便,此处将环也视作基环树。
先将确定的边连上,根据上述结论,如果一个连通块是基环树,无论剩下的边怎么连,这都是一个独立的连通块。贡献为 \(n^{cnt}\),其中 \(cnt\) 表示还没连的边的数量。
剩下的就是树的部分,以这棵树中的 \(-1\) 节点为根。如果它连到了一个基环树上,那么肯定没有贡献,所以不考虑,只考虑树与树之间的相连带了的贡献。因为最后一定是基环树,所以我们的问题就是基环树的环是怎么组成。假定形成的环是由 \(x\) 棵树组合而成,设 \(f_{i,j}\) 表示仅使用树 \([1,j]\) 形成大小为 \(i\) 的环的方案数,\(siz_j\) 表示树 \(j\) 的大小。可以得到转移 \(f_{i,j}=f_{i,j-1}+f_{i-1,j-1}*\max(j-1,1)*siz_j\)。
容易理解,若 \(i\not= 1\),任选原来的一种由 \(i-1\) 个树构成的环,选择断掉原来一个树连到另一个树上的边,并自己连到这条边原来的终点共有 \(j-1\) 种方案,如果 \(i=1\) 则是往自己连边,共有 \(1\) 种方。,此时原来的断掉的边还没有终点,可以将其连到当前这棵树上的任意点,共有 \(siz_j\) 种方案。无论剩下的树怎么连,这颗由 \(i\) 棵树组成的基环树都会产生贡献,贡献为 \(n^{cnt-i}\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2010,mod=998244353;
int n,a[N],siz[N],val[N],cnt,vis[N],fac[N],Pow[N],f[N],ans;
vector<int>e[N];
void dfs(int u){
vis[u]=siz[u]=1;
for(auto v:e[u]){
if(!vis[v]){
dfs(v);
siz[u]+=siz[v];
}
}
}
void solve(){
read(n);
fac[0]=Pow[0]=1;
for(int i=1;i<=n;i++){
fac[i]=1ll*fac[i-1]*i%mod;
Pow[i]=1ll*Pow[i-1]*n%mod;
}
for(int i=1;i<=n;i++){
read(a[i]);
if(~a[i]){
e[i].pb(a[i]);
e[a[i]].pb(i);
}
}
for(int i=1;i<=n;i++){
if(!(~a[i])){
dfs(i);
val[++cnt]=siz[i];
}
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
ans=(ans+Pow[cnt])%mod;
}
}
f[0]=1;
for(int i=1;i<=cnt;i++){
for(int j=i;j;j--){
f[j]=(f[j]+1ll*f[j-1]*val[i]%mod*max(j-1,1)%mod)%mod;
}
}
for(int i=1;i<=cnt;i++){
ans=(ans+1ll*f[i]*Pow[cnt-i]%mod)%mod;
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Buying gifts
题面
以 \(a\) 为关键字排序,枚举钦定哪个为 \(a\) 的最大值,那么 \(a\) 中大于这个的部分必选 \(b\)。维护这些必选的数的最大值。
若大于钦定的 \(a\) 的最大值,那么此时差的最小值就为两个数之差;若小于,维护前面可选的数中大于钦定的 \(a\) 的最小值和小于钦定的 \(a\) 的最大值。用 multiset 维护这三个信息即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10,inf=1e9;
int n;
pii a[N<<1];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i].first),read(a[i].second);
}
sort(a+1,a+n+1);
multiset<int>s_bac,s_front;
for(int i=1;i<=n;i++){
s_bac.insert(a[i].second);
}
int less=-inf,ans=inf;
for(int i=1;i<=n;i++){
s_bac.erase(s_bac.find(a[i].second));
while(s_front.size()&&*s_front.begin()<a[i].first){
less=max(less,*s_front.begin());
s_front.erase(s_front.begin());
}
int bac_mx=-inf;
if(s_bac.size()){
auto it=s_bac.end();
it--;
bac_mx=*it;
}
if(bac_mx>=a[i].first){
ans=min(ans,bac_mx-a[i].first);
}
else{
int mn=a[i].first-less;
mn=min(a[i].first-bac_mx,mn);
if(s_front.size()){
mn=min(mn,*s_front.begin()-a[i].first);
}
ans=min(ans,mn);
}
s_front.insert(a[i].second);
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
Tweetuzki 爱序列
题面
如果数 \(x,y\) 满足 \(x\) 可以通过一次两操作之一变为 \(y\),从 \(x\) 向 \(y\) 连边,得到的图一定是个拓扑图。
证明:设 \(\div 3\) 操作进行了 \(a\) 次,\(\times 2\) 操作进行了 \(b\) 次,\(3^{-a}\times 2^b=1\),\(2^b=3^a\) ,因为 \(a,b>0\),所以无正整数解。因此生成的图一定为拓扑图,直接dp即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int f[N],a[N],nxt[N],val[N],n,m,ans_num,ans_pos;
vector<int>e[N];
int find(int x){
int l=1,r=m;
while(l<=r){
int mid=(l+r)>>1;
if(val[mid]>x){
r=mid-1;
}
else if(val[mid]<x){
l=mid+1;
}
else{
return mid;
}
}
return 0;
}
int dfs(int u){
if(f[u]){
return f[u];
}
f[u]=1;
for(auto v:e[u]){
if(dfs(v)+1>f[u]){
f[u]=f[v]+1;
nxt[u]=v;
}
}
return f[u];
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
val[i]=a[i];
}
sort(val+1,val+n+1);
m=unique(val+1,val+n+1)-val-1;
for(int i=1;i<=m;i++){
int x=find(val[i]*2),y=0;
if(val[i]%3==0){
y=find(val[i]/3);
}
if(x){
e[i].pb(x);
}
if(y){
e[i].pb(y);
}
}
for(int i=1;i<=m;i++){
dfs(i);
if(f[i]>ans_num){
ans_num=f[i];
ans_pos=i;
}
}
write_endl(ans_num);
while(ans_pos){
write_space(val[ans_pos]);
ans_pos=nxt[ans_pos];
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Ryoku 与最初之人笔记
题面
有趣题,直接模异或肯定没什么想法,考虑拆开。一般拆异或有两种拆法,拆位或者变为或减与,显然这里后者是可做的。
\(a\) 或 \(b\) 中为 \(1\) 的位置可以变成 \(a\) 与 \(b\) 中为 \(1\) 的位置并只有 \(a\) 为 \(1\) 的位置并只有 \(b\) 为 \(1\) 的位置。令三个部分的权值分别为 \(x,y,z\)。式子转化为 \(x+y\equiv x+z\pmod {y+z}\),再化一步得 \(z-y\equiv 0 \pmod {y+z}\),\(z-y=k(z+y)\)。因为 \(k,y,z\ge 1\),所以 \(y=0\),也就是 $a& b=a。
求这样的数对的对数,直接枚举 \(b\) 中 \(1\) 的个数,求 \(1\) 的个数为 \(s\) 时的数的个数,此时 \(a\) 的选择方案数有 \(2^s-1\) 种,求个数时用数位dp求解即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=100,mod=1e9+7;
int n,num[N],f[N][N][10],cnt,ans;
int dfs(int now,int tot,int flag){
if(tot<0){
return 0;
}
if(!now){
if(!tot){
return 1;
}
return 0;
}
if(f[now][tot][flag]!=-1){
return f[now][tot][flag];
}
f[now][tot][flag]=0;
for(int i=0;i<=(flag?num[now]:1);i++){
f[now][tot][flag]=(f[now][tot][flag]+dfs(now-1,tot-i,flag&&(i==num[now])))%mod;
}
return f[now][tot][flag];
}
int calc(int k){
memset(f,-1,sizeof(f));
int res=dfs(cnt,k,1);
return res;
}
void solve(){
read(n);
while(n){
num[++cnt]=n%2;
n/=2;
}
for(int i=1;i<=cnt;i++){
ans=(ans+((1ll<<i)%mod-1+mod)%mod*calc(i)%mod)%mod;
}
// calc(1);
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}