A
只要打个表就能发现,1,6,8,9的所有排列就可以产生0~6的余数了...
所以...走不下去的时候一定要打表...
#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define mid ((l+r)>>1)
#define ls ((rt<<1))
#define rs ((rt<<1)+1)
#define maxn 1000100
char s[maxn];
string s2,f[];
int n,cnt[],m[]={,,,};
int getr(string t){
int r=;
rep(i,(int)t.size()){
int cur=t[i]-'';
r = (r*+cur)%;
}
// cout<<"string="<<t<<" r="<<r<<endl;
return r;
}
bool vis[];
void dfs(int step,string cur){
if (step==){
f[getr(cur)]=cur;
return;
}
// cout<<cur<<endl;
for (int i= ; i< ; i++ ) if (!vis[m[i]]){
vis[m[i]]=;
dfs(step+,cur+(char)(m[i]+''));
vis[m[i]]=;
}
}
int main(){
// freopen("test","r",stdin);
dfs(,(string)"");
scanf("%s",s);
n = strlen(s);
rep(i,n) cnt[s[i]-'']++;
rep(i,) cnt[m[i]]--;
s2 = "";
for (int i= ; i<= ; i++ ){
rep(j,cnt[i]) s2 += (char)(i+'');
}
int len = n-s2.size()-cnt[];
string s1 = s2;
rep(i,len) s1 += '';
int r = getr(s1);
s2 += f[(-r)%];
rep(i,cnt[]) s2 += '';
getr(s2);
cout<<s2<<endl;
return ;
}
B
首先,想象一下,找到最大的矩形,可以看作在一些右端点对齐的线段中找到最大的矩形,然后枚举列就可以了,
然后注意到"能重排row"这个条件,把所有线段按长度排序,扫一遍就能更新出最大,这个复杂度是 O(n*n*logn)的,
最后,规模只有5000,排序可以用O(n)的基数排序,复杂度O(n*n).
#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llong;
#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define mid ((l+r)>>1)
#define ls ((rt<<1))
#define rs ((rt<<1)+1)
#define maxn 5001
int n,m,h[maxn],idx[maxn];
char g[maxn][maxn];
bool cmp(int x,int y){return x>y;}
int main(){
// freopen("test","r",stdin);
scanf("%d%d",&n,&m);
int area=;
rep(r,n) scanf("%s",g[r]);
vector<int>rcd;
rep(c,m){
// printf("add col:%d\n",c);
rep(r,n) {
h[r]=(g[r][c]=='')?h[r]+:;
// printf("g[%d][%d]=%d h[%d]=%d \n",r,c,g[r][c],r,h[r]);
}
rcd.clear();
rep(r,n) if(h[r]) rcd.push_back(h[r]);
sort(rcd.begin(),rcd.end(),cmp);
rep(i,(int)rcd.size()) area=max(area,rcd[i]*(i+));
}
printf("%d\n",area);
return ;
}
C
本来以为是一道插头dp之类的...但是分析可以发现:
1.特殊点<=8,可以状压;
2.每走一步,可以确定当前轮廓中有哪些特殊点(根据题面给出的算法);
于是可以转化为一个最短路问题:
dist[i][j][mask], 到达(i,j)点的状态为mask时的最大价值,
为了合法,最后答案的mask中代表'B'的位为0.
总复杂度O(n*m*28*4*8)
typedef long long llong;
#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define mid ((l+r)>>1)
#define ls ((rt<<1))
#define rs ((rt<<1)+1)
#define maxn 21
#define MASK (1<<8)
char g[maxn][maxn];
int n,m,id[maxn][maxn],cv,cb,var[MASK],
dr[]={,,-,},
dc[]={,,,-},
d[maxn][maxn][MASK];
bool inq[maxn][maxn][MASK];
struct node{
int r,c,msk;
};queue<node> q;
vector<node> b;
void input(){
scanf("%d%d",&n,&m);
rep(i,n) scanf("%s",g[i]);
memset(id,-,sizeof(id));
rep(i,n) rep(j,m) if (isdigit(g[i][j]))
id[i][j]=g[i][j]-'',cv++;
rep(i,n) rep(j,m) if (g[i][j]=='B')
id[i][j]=cv+(cb++);
rep(i,n) rep(j,m) {
if (g[i][j]=='B')
b.push_back((node){i,j,(<<id[i][j]>>cv)});
if (isdigit(g[i][j]))
b.push_back((node){i,j,(<<id[i][j]<<cb)});
}
rep(i,cv) scanf("%d",&var[<<i]);
}
int lowbit(int x) {return x&(-x);}
void pretreat(){
rep(i,MASK) if (i) var[i]=var[i-lowbit(i)]+var[lowbit(i)];
}
bool invalid(node cur){
if (cur.r<||cur.r>=n||cur.c<||cur.c>=m) return true;
if (id[cur.r][cur.c]!=-) return true;
if (g[cur.r][cur.c]=='#') return true;
return false;
}
void updata(node nxt,int x){
if (d[nxt.r][nxt.c][nxt.msk]==- || d[nxt.r][nxt.c][nxt.msk]>x){
d[nxt.r][nxt.c][nxt.msk]=x;
if (!inq[nxt.r][nxt.c][nxt.msk]){
inq[nxt.r][nxt.c][nxt.msk]=;
q.push(nxt);
}
}
}
int bfs(){
memset(d,-,sizeof(d));
memset(inq,,sizeof(inq));
node cur,nxt;
int ans=;
rep(i,n) rep(j,m) if (g[i][j]=='S'){
q.push((node){i,j,});
d[i][j][]=;
inq[i][j][]=;
break;
}
while (!q.empty()){
cur = q.front(); q.pop();
inq[cur.r][cur.c][cur.msk]=;
if (g[cur.r][cur.c]=='S' && ((cur.msk&((<<cb)-))==) )
ans = max(ans,var[cur.msk>>cb]-d[cur.r][cur.c][cur.msk]);
rep(i,){
nxt.r = cur.r+dr[i];
nxt.c = cur.c+dc[i];
if (invalid(nxt)) continue;
if (i&){
nxt.msk=cur.msk;
rep(j,(int)b.size()) {
if (i==) {
if (b[j].r>nxt.r && b[j].c==nxt.c) nxt.msk^=b[j].msk;
} else {
if (b[j].r>cur.r && b[j].c==cur.c) nxt.msk^=b[j].msk;
}
}
}else nxt.msk = cur.msk;
updata(nxt,d[cur.r][cur.c][cur.msk]+);
}
}
return ans;
}
int main(){
input();
pretreat();
printf("%d\n",bfs());
return ;
}
trick:
判断点是否在轮廓中时,只要考虑一个方向的射线;
同一个点向相反的方向走,在mask中更新的点不一样.
D
合并树:
以col为关键字造平衡树,回答在u上询问时,先递归回答它所有子树的询问;
然后合并子树,更新k值,因为每加入一个节点,k变化一次,所以均摊复杂度O(n),合并树的总复杂度O(nlogn);
朴素做法:
共用2个数组记录颜色频率feq和k值,回答u询问时,先递归回答它子树询问,
回溯时删除之前递归产生的统计,然后递归到下一个子树...
for x in e[u]:
dfs(x),del(x);
最后加入所有子树,回答u上的询问:
for x in e[u]:
add(x);
这样的做法是O(n2)的.
优化:
最大的子树不进行del和add操作,可以优化为O(nlogn).
分析:
对于节点v,它被del时的祖先为u,那么size[u]>=2*size[v],所以v最多有logn个这样的祖先u,即它最多被执行longn次del操作,
add操作比del操作多一次.
#define rep(i,n) for(int i=0 ; i<(n) ; i++ )
#define ls ((rt)<<1)
#define rs (((rt)<<1)+1)
#define mid ((l+r)>>1)
#define maxn 100100
vector<int> e[maxn],q[maxn];
int qk[maxn],sz[maxn],n,m,col[maxn],cnt[maxn],f[maxn],ans[maxn]; void add(int x,int fa){
cnt[col[x]]++;
f[cnt[col[x]]]++;
rep(i,(int)e[x].size()) if(e[x][i]!=fa)
add(e[x][i],x);
}
void del(int x,int fa){
f[cnt[col[x]]]--;
cnt[col[x]]--;
rep(i,(int)e[x].size()) if(e[x][i]!=fa){
del(e[x][i],x);
}
}
void dfs(int cur,int fa){
int big=-,idx=-;
rep(i,(int)e[cur].size()) if(e[cur][i]!=fa){
if (sz[e[cur][i]]>big){
big = sz[e[cur][i]];
idx = i;
}
}
rep(i,(int)e[cur].size()) if(e[cur][i]!=fa){
if (i==idx) continue;
dfs(e[cur][i],cur);
del(e[cur][i],cur);
}
if (idx!=-) dfs(e[cur][idx],cur);
cnt[col[cur]]++;
f[cnt[col[cur]]]++;
rep(i,(int)e[cur].size()) if(e[cur][i]!=fa){
if (i==idx) continue;
add(e[cur][i],cur);
}
rep(i,(int)q[cur].size()){
int id = q[cur][i];
int k = qk[id];
ans[id] = f[k];
}
}
void initsz(int x,int fa){
sz[x]=;
rep(i,(int)e[x].size()) if(e[x][i]!=fa){
initsz(e[x][i],x);
sz[x] += sz[e[x][i]];
}
}
int main(){
// freopen("test.txt","r",stdin);
scanf("%d%d",&n,&m);
for (int i= ; i<=n ; i++ ) scanf("%d",&col[i]);
for (int i= ; i<n ; i++ ){
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
initsz(,);
rep(i,m){
int k,x;
scanf("%d%d",&x,&k);
q[x].push_back(i);
qk[i]=k;
}
dfs(,);
rep(i,m) printf("%d\n",ans[i]);
return ;
}
E
第一步可以把问题转化为:求用不超过cntb个的黑点覆盖整个树的最小代价,在本来是黑点处放黑点代价为0,在红点处放黑点代价为1;
然后当假设总共用了i个黑点,问题貌似就能表示为一个容量为i的背包了:
dp[u][i] 表示u为根的子树用i个黑点覆盖的最小代价;
不过还有一个问题:u被覆盖的情况很复杂,可能覆盖点来自u这颗子树的外面.
于是需要再加以为来描述覆盖u的点:
dp[u][i][w] 表示u为根的子树,用i个黑点覆盖,此外u已经被w覆盖 的最小代价.
最后我们的答案就是 best[0][i] = min{dp[0][i][w]} (0<i<=cntb , 0<=w<n);
using namespace std;
#define rep(i,n) for(int i=0 ; i<(n) ; i++ )
#define ls ((rt)<<1)
#define rs (((rt)<<1)+1)
#define mid ((l+r)>>1)
#define maxn 501
#define INF 10001
struct node{
int v,w;
};vector<node> e[maxn];
short dp[maxn][maxn][maxn];
int dp2[maxn][maxn],best[maxn][maxn],
col[maxn],dist[maxn][maxn],n,x,sz[maxn]; void initdist(int u,int fa,int rt,int d) {
if (d>=x+) d=x+;
dist[rt][u]=d;
rep (i,(int)e[u].size()) {
if (e[u][i].v==fa) continue;
initdist(e[u][i].v,u,rt,d+e[u][i].w);
}
} void dfs(int u,int fa) {
int chd[maxn],nch=;
sz[u]=;
rep (i,(int)e[u].size()) {
if (e[u][i].v==fa) continue;
dfs(e[u][i].v,u);
chd[nch++]=e[u][i].v;
sz[u] += sz[e[u][i].v];
}
// printf("*********************************\n");
// printf("u:%d\n",u);
rep (w,n) {
if (dist[u][w]>x) continue;
if (nch) {
int tot=,c,c1;
c = chd[];
tot += sz[c];
rep (i,tot)
dp2[c][i] = min((int)dp[c][i][w],best[c][i]);
for (int i= ; i<nch- ; i++ ) {
c = chd[i];
c1 = chd[i+];
rep (j,tot+sz[c1]+) dp2[c1][j] = INF;
rep (j,tot) rep(k,sz[c1]+) {
if (k<sz[c1]) dp2[c1][j+k] = min(dp2[c1][j+k],dp2[c][j]+dp[c1][k][w]);
dp2[c1][j+k] = min(dp2[c1][j+k],dp2[c][j]+best[c1][k]);
}
tot += sz[c1];
}
}
// printf("w:%d\n",w);
// rep (i,nch) rep (j,sz[u]+1) printf("dp2[%d][%d]=%d\n",chd[i],j,dp2[chd[i]][j]);
rep (i,sz[u]) {
if (nch) dp[u][i][w] = dp2[chd[nch-]][i];
else dp[u][i][w] = ;
// printf("dp[%d][%d][%d]=%d\n",u,i,w,dp[u][i][w]);
}
rep (i,sz[u]) {
best[u][i+] = min(best[u][i+],dp[u][i][w]+(col[w]==));
}
}
// rep (i,sz[u]+1) printf("best[%d][%d]=%d\n",u,i,best[u][i]);
// printf("*********************************\n");
} void solv() {
rep (i,n) initdist(i,-,i,);
rep (i,maxn) rep (j,maxn) rep (k,maxn) dp[i][j][k]=INF;
rep (i,maxn) rep (j,maxn) dp2[i][j]=INF,best[i][j]=INF;
dfs(,-);
int ans = INF;
int cntb=;
rep (i,n) cntb += col[i];
rep (i,cntb+) ans = min(ans,best[][i]);
printf("%d\n",ans==INF?-:ans);
} int main(){
// freopen("test.txt","r",stdin);
scanf("%d%d",&n,&x);
rep (i,n) scanf("%d",&col[i]);
rep (i,n-) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u--, v--;
e[u].push_back((node){v,w});
e[v].push_back((node){u,w});
}
solv();
return ;
}
背包部分的复杂度:
看起来似乎每次dfs,背包部分的复杂度是o(n^2)的,但实际整个过程中,对于每个w,每对lca恰好访问一次,所以均摊复杂度是 O(n2),总复杂度O(n3)
(p.s 最开始仿照rank1的写法dp,然后发现dp2的下标可以用直接用节点编号就不用每次dfs都初始化1次,于是后面按自己想法写...
最后发现答案偏小了,呆看了一阵发现,枚举w的时候dp2也需要初始化...)
这套题的D,E还蛮考复杂度分析的,涨姿势了...