T1这道题不难，当时做的时候忘记一张牌正反面可能相同的情况，然后就GG了
数字太大，用数组记不下了
方法1：map
方法2：离散化，使得数字值域落在2n以内
T2这道题类似于逆序对，实质上就是求逆序对的个数，然而这道题是求逆序字
符串的个数，可以用归并排序来求解逆序对的个数归并排序时比较两个数字的
大小，归并排序时比较两个字符串的字典序大小
决定两个字符串字典序大小的是从左到右第一位不相同的字符
二分+哈希找到第一位不相同的位
数字O(1)比较大小 字符串O(logn)比较大小
归并排序O(nlogn)
总复杂度O(nlog2n)
T3小数据搜索，大数据状态压缩DP+记忆化搜索
F[i1][i2][j1][j2][sta]表示从子矩形(i1,j1)-(i2,j2)中能否刚好切出sta中的巧克力
最终答案为F[1][n][1][m][2k-1]
转移时枚举横切/竖切，以竖切为例
再枚举sta’，表示sta’中的巧克力被分到左边，其余分到右边
根据sta’中的巧克力面积和可以算出左边应该切多长（k），或者无法切
怎么算？二分或枚举
转移类似
j2那维在存储时可以省去
T1纸牌
#include <cstdio> #include <algorithm> #define inf 1000000007 #define N 500055 int n,i,x,y,top[N*2],bot[N*2],ans,hf,lst,p; struct T { int v, f; }; T a[N*2]; bool cmpv(const T &a, const T &b) { return a.v < b.v; } bool cmpf(const T &a, const T &b) { return a.f < b.f; } int main() { freopen("card.in", "r", stdin); freopen("card.out", "w", stdout); scanf("%d",&n); for (i=1; i<=n; ++i) { scanf("%d%d", &a[i*2-1].v, &a[i*2].v); a[i*2-1].f = i*2-1; a[i*2].f = i*2; } std::sort(a+1, a+n*2+1, cmpv); lst = -1; for (i=1; i<=n*2; ++i) { p += (lst!=a[i].v); lst = a[i].v; a[i].v = p; } std::sort(a+1, a+n*2+1, cmpf); for (i=1; i<=n; ++i) { x = a[i*2-1].v; y = a[i*2].v; ++top[x]; if (x!=y) ++bot[y]; } hf = (n+1)/2; ans = inf; for (i=1; i<=p; ++i) { if (top[i]+bot[i] < hf) continue; if (top[i] >= hf) { ans = 0; break; } if (hf-top[i] < ans) ans = hf-top[i]; } if (ans == inf) printf("Impossible "); else printf("%d ",ans); return 0; }
T2 后缀数组
#include <cstdio> #define mo 1000000007 #define N 50055 int f[N],s[N],tmp[N],n,m,i,ch,ans; long long hash[N],pow[N]; //二分+哈希求以i开头的和以j开头的两个子串哪个字典序更小 bool lessThanOrEqual(int i, int j) { if (i == j) return true; int l, r, k; long long hsi, hsj; //二分求i和j开始从左向右第一位不同的位 l = 0; r = m+1; if (n-j+2 < r) r = n-j+2; if (n-i+2 < r) r = n-i+2; while (r-l > 1) { k = (l+r)/2; //子串[i,i+k-1]的哈希值 hsi = hash[i+k-1]-hash[i-1]*pow[k]%mo; if (hsi < 0) hsi += mo; //子串[j,j+k-1]的哈希值 hsj = hash[j+k-1]-hash[j-1]*pow[k]%mo; if (hsj < 0) hsj += mo; if (hsi == hsj) l = k; else r = k; } //s[i+l]和s[j+l]是第一位不同的位 if (l == m) return true; return s[i+l] < s[j+l]; } //归并排序 void sort(int l, int r) { if (l == r) return; int mi = (l+r)/2; sort(l, mi); sort(mi+1, r); int i=l, j=mi+1; int nt = l; while (i<=mi || j<=r) { bool ilej; if (i > mi) ilej = false; else if (j > r) ilej = true; else ilej = lessThanOrEqual(f[i],f[j]); if (ilej) tmp[nt++] = f[i++]; else { tmp[nt++] = f[j++]; //从右区间取数时，右区间和左区间之间产生了继续对 //累加答案 ans += mi-i+1; } } for (i=l; i<=r; ++i) f[i] = tmp[i]; } int main() { freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout); scanf("%d%d", &n, &m); hash[0] = 0; pow[0] = 1; for (i=1; i<=n; ++i) { for (ch=getchar(); ch<=32; ch=getchar()); s[i] = ch-96; //预处理hash[i]=子串[1,i]的哈希值 hash[i] = (hash[i-1]*29+s[i])%mo; //预处理pow[i]=29^i pow[i] = pow[i-1]*29%mo; f[i] = i; } s[n+1] = 0; sort(1, n); printf("%d ", ans); return 0; }
T3巧克力
#include <cstdio> #include <list> #define MAXK 15 #define N 11 struct Quad { int a, b, c, d; Quad(int _a, int _b, int _c, int _d): a(_a), b(_b), c(_c), d(_d) {} }; std::list<Quad> lf, lfx, lfy; char f[N][N][N][1<<MAXK],fx[N][N][N][1010],fy[N][N][N][1010]; int sumx[N][N][N],sumy[N][N][N],suma[1<<MAXK],bg[1<<MAXK],ed[1<<MAXK],c[15000000],e[MAXK+1],a[20], n,m,K,i,j,l,r,T,sta,nc,w; /* 求：以j1为左边界、j2为右边界、i1为上边界的矩形中，下边界为多少的矩形 重量和是w。如果不存在则返回-1 用二分求 */ int calcx(int j1, int j2, int i1, int w) { // fx[j1][j2][i1][w]用于记录该子问题有没有被求结果 // 已求结果则直接返回结果 if (fx[j1][j2][i1][w] != 0) return fx[j1][j2][i1][w]; // 未求结果，将该状态加入待清空队列 lfx.push_back(Quad(j1,j2,i1,w)); // 二分求i2的位置 int l, r, k; l = i1-1; r = n+1; while (r-l > 1) { k = l+r>>1; if (sumx[j1][j2][k]-sumx[j1][j2][i1-1] <= w) l = k; else r = k; } if (sumx[j1][j2][l]-sumx[j1][j2][i1-1] != w) l = -1; return fx[j1][j2][i1][w]=l; } /* 求：以i1为上边界、i2为下边界、j1为左边界的矩形中，右边界为多少的矩形 重量和是w。如果不存在则返回-1 和上面对称 */ int calcy(int i1, int i2, int j1, int w) { if (fy[i1][i2][j1][w] != 0) return fy[i1][i2][j1][w]; lfy.push_back(Quad(i1,i2,j1,w)); int l, r, k; l = j1-1; r = m+1; while (r-l > 1) { k = l+r>>1; if (sumy[i1][i2][k]-sumy[i1][i2][j1-1] <= w) l = k; else r = k; } if (sumy[i1][i2][l]-sumy[i1][i2][j1-1] != w) l = -1; return fy[i1][i2][j1][w]=l; } /* 求(i1,j1)~(i2,j2)的矩形能否切出sta中的巧克力 */ bool work(int i1, int i2, int j1, int j2, int sta) { //记忆化：求过了则直接返回 if (f[i1][i2][j1][sta] != 0) return f[i1][i2][j1][sta]==1; if (bg[sta] == ed[sta]) return true; //未求过，将该状态加入待清空队列 lf.push_back(Quad(i1,i2,j1,sta)); int i, sta2, x, y; //枚举sta的每个非空真子集 for (i=bg[sta]; i<ed[sta]; ++i) { sta2 = c[i]; //尝试横向切 x = calcx(j1,j2,i1,suma[sta2]); if (x != -1) if (work(i1,x,j1,j2,sta2) && work(x+1,i2,j1,j2,sta-sta2)) { f[i1][i2][j1][sta] = 1; return true; } //尝试纵向切 y = calcy(i1,i2,j1,suma[sta2]); if (y != -1) if (work(i1,i2,j1,y,sta2) && work(i1,i2,y+1,j2,sta-sta2)) { f[i1][i2][j1][sta] = 1; return true; } } f[i1][i2][j1][sta] = -1; return false; } void dfs(int sta, int t) { if (t == MAXK) { if (sta > 0) c[nc++] = sta; return; } if (sta&e[t]) dfs(sta-e[t], t+1); dfs(sta, t+1); } int main() { freopen("chocolate.in", "r", stdin); freopen("chocolate.out", "w", stdout); e[0] = 1; for (i=1; i<=MAXK; ++i) e[i] = e[i-1]*2; //预处理每个sta有哪些非空真子集，连续存储在队列c中 nc = 1; for (sta=1; sta<e[MAXK]; ++sta) { bg[sta] = nc; //bg表示sta的子集在c中的开头位置 dfs(sta, 0); //dfs求sta的非空真子集 --nc; ed[sta] = nc; //ed表示sta的子集在c中的结尾位置 } scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &m, &K); for (i=1; i<=n; ++i) for (j=1; j<=m; ++j) { scanf("%d", &w); //sumy[i][j][k]:从第i行到第j行，从第1列到第k列构成的矩形的重量和 sumy[i][i][j] = sumy[i][i][j-1]+w; //sumx[i][j][k]:从第i列到第j列，从第1行到第k行构成的矩形的重量和 sumx[j][j][i] = sumx[j][j][i-1]+w; } for (l=1; l<n; ++l) for (r=l+1; r<=n; ++r) for (j=1; j<=m; ++j) sumy[l][r][j] = sumy[l][r-1][j]+sumy[r][r][j]; for (l=1; l<m; ++l) for (r=l+1; r<=m; ++r) for (i=1; i<=n; ++i) sumx[l][r][i] = sumx[l][r-1][i]+sumx[r][r][i]; for (i=1; i<=K; ++i) scanf("%d", &a[i]); //求出{ai}的各个子集的重量和 //suma[sta]：sta中的巧克力的总重量 for (sta=0; sta<e[K]; ++sta) { suma[sta] = 0; for (i=sta, j=1; i>0; i>>=1, ++j) if (i&1) suma[sta] += a[j]; } // 如果所有ai的总重量!=巧克力的总重量 if (suma[e[K]-1] != sumy[1][n][m]) { printf("no "); continue; } //lf、lfx、lfy用于记录哪些状态被记忆化了，用于之后清零 lf.clear(); lfx.clear(); lfy.clear(); if (work(1,n,1,m,e[K]-1)) printf("yes "); else printf("no "); //清零记忆化过的状态 for (std::list<Quad>::iterator it=lf.begin(); it!=lf.end(); ++it) f[it->a][it->b][it->c][it->d] = 0; for (std::list<Quad>::iterator it=lfx.begin(); it!=lfx.end(); ++it) fx[it->a][it->b][it->c][it->d] = 0; for (std::list<Quad>::iterator it=lfy.begin(); it!=lfy.end(); ++it) fy[it->a][it->b][it->c][it->d] = 0; } return 0; }