@KirinBill
2017-10-26T17:27:50.000000Z
字数 5586
阅读 1180
题解
套题
目录
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <cstring>
const int MAXN=100005;
int n;
char s[MAXN];
class segT{
private:
struct data{
int tag;
int c[26];
void clear(){
tag=0;
memset(c,0,sizeof(c));
}
data(){clear();}
int& operator [](int i){return c[i];}
void operator ()(int cnt,data &that){
clear();
tag=that.tag;
//1 up,-1 dwn
for(int i= tag>0 ? 0:25;0<=i && i<26;i+=tag){
if(that[i]>=cnt){
c[i]=cnt;
that[i]-=cnt;
return;
}
else{
c[i]=that[i];
cnt-=that[i];
that[i]=0;
}
}
}
data operator +(const data &that)const{
data ret;
for(int i=0;i<26;++i)
ret[i]=c[i]+that.c[i];
return ret;
}
data& operator +=(const data &that){
*this=*this+that;
return *this;
}
};
struct node{
int l,r,ls,rs;
data c;
int len(){return r-l+1;}
}d[MAXN<<2];
int new_nd(){
static int cnt=1;
return ++cnt;
}
void upd(int u){
d[u].c=d[d[u].ls].c+d[d[u].rs].c;
}
void push_d(int u){
if(!d[u].c.tag) return;
int ls=d[u].ls,rs=d[u].rs;
data tmp=d[u].c;
d[ls].c(d[ls].len(),tmp);
d[rs].c(d[rs].len(),tmp);
d[u].c.tag=0;
}
data qry(int u,int lp,int rp){
if(lp<=d[u].l && d[u].r<=rp)
return d[u].c;
push_d(u);
int mid=d[u].l+d[u].r>>1;
data ret;
if(lp<=mid) ret=qry(d[u].ls,lp,rp);
if(rp>mid) ret+=qry(d[u].rs,lp,rp);
return ret;
}
void mdf(int u,int lp,int rp,data &sum){
if(lp<=d[u].l && d[u].r<=rp){
d[u].c(d[u].len(),sum);
return;
}
push_d(u);
int mid=d[u].l+d[u].r>>1;
if(lp<=mid) mdf(d[u].ls,lp,rp,sum);
if(rp>mid) mdf(d[u].rs,lp,rp,sum);
upd(u);
}
void prt(int u){
if(d[u].l==d[u].r){
for(int i=0;i<26;++i){
if(d[u].c[i]){
s[d[u].l]=i+'a';
return;
}
}
}
push_d(u);
int mid=d[u].l+d[u].r>>1;
prt(d[u].ls),prt(d[u].rs);
}
void build(int u,int l,int r){
d[u].l=l,d[u].r=r;
if(l==r){
d[u].c[s[l]-'a']=1;
return;
}
int mid=l+r>>1;
d[u].ls=new_nd();
build(d[u].ls,l,mid);
d[u].rs=new_nd();
build(d[u].rs,mid+1,r);
upd(u);
}
public:
void build(){build(1,1,n);}
void sort(int lp,int rp,int type){
type= type ? 1:-1;
data sum=qry(1,lp,rp);
sum.tag=type;
mdf(1,lp,rp,sum);
}
void prt(){prt(1);}
}T;
int main(){
setIO("string");
int m;
read(n),read(m);
scanf("%s",s+1);
T.build();
for(int i=1,l,r,type;i<=m;++i){
read(l),read(r),read(type);
T.sort(l,r,type);
}
T.prt();
printf("%s",s+1);
return 0;
}
#include <cstdio>
const int MAXN=3005,P=998244353;
int n,m;
int l[MAXN],r[MAXN],prel[MAXN],prer[MAXN];
inline int DP(){
static int dp[MAXN][MAXN];
dp[0][0]=1;
for(int i=1;i<=m;++i){
dp[i][0]=dp[i-1][0];
for(int j=1;j<=i && prer[i]>=j-1;++j)
dp[i][j]=(dp[i-1][j]+(long long)dp[i-1][j-1]*(prer[i]-(j-1))%P)%P;
for(int j=prel[i-1];j<prel[i];++j){
for(int k=0;k+j<=i;++k)
dp[i][k]=(long long)dp[i][k]*(i-j-k)%P;
}
}
return dp[m][n];
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d%d",&l[i],&r[i]);
++prel[l[i]],++prer[r[i]];
}
for(int i=1;i<=m;++i){
prel[i]+=prel[i-1];
prer[i]+=prer[i-1];
}
printf("%d",DP());
return 0;
}
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
#include <functional>
using std::sort;
using std::greater;
const int MAXM=100005,MAXN=30;
int n,m;
int a[MAXM],xor_suf[MAXM],ans[MAXM];
class Trie{
private:
int c[MAXM*MAXN][2];
int new_nd(){
static int cnt;
return ++cnt;
}
void trans(int u,int step,int num){
if(step<0){
ans[++ans[0]]=num;
return;
}
if(!c[u][0] && c[u][1])
trans(c[u][1],step-1,num|1<<step);
else if(!c[u][1] && c[u][0])
trans(c[u][0],step-1,num|1<<step);
else if(c[u][0] && c[u][1]){
trans(c[u][0],step-1,num);
trans(c[u][1],step-1,num);
}
}
public:
void ist(int x){
for(int u=0,i=n-1;i>=0;--i){
if(!c[u][(bool)(x&1<<i)])
c[u][(bool)(x&1<<i)]=new_nd();
u=c[u][(bool)(x&1<<i)];
}
}
void trans(){trans(0,n-1,0);}
}T;
int main(){
setIO("big");
read(n),read(m);
for(int i=1;i<=m;++i)
read(a[i]);
for(int i=m;i;--i)
xor_suf[i]=a[i]^xor_suf[i+1];
for(int i=0,xor_pre=0;i<=m;++i){
xor_pre^=a[i];
T.ist((xor_pre<<1>>n)+(xor_pre<<1)&(1<<n)-1^xor_suf[i+1]);
}
T.trans();
sort(ans+1,ans+ans[0]+1,greater<int>());
write(ans[1],'\n');
int cnt=0;
for(int i=1;ans[i]==ans[1] && i<=ans[0];++i)
++cnt;
write(cnt);
return 0;
}