期望得分：100+50+20=170
实际得分：10+50+20=80
1. 纸牌
题目描述
在桌面上放着n张纸牌，每张纸牌有两面，每面都写着一个非负整数。你的邪王真眼可以看到所有牌朝上的一面和朝下的一面写的数字。现在你需要将一些牌翻过来，使得所有牌朝上的一面中，至少有一半（≥n/2）的数字是一样的。请你求出最少需要翻几张牌，或者判断无解。
注意：在翻牌的时候，你不能把牌扔掉，不能偷偷把别的牌放进来，也不能用笔涂改牌上面的数字。
输入格式
第一行包含一个整数n，表示牌的数量；
接下来n行，每行两个非负整数ai, bi，表示每张牌上写的两个数字，ai对应朝上的一面，bi对应朝下的一面。
输出格式
如果有解，则输出一个整数，表示最少的翻牌次数，否则输出Impossible。
样例输入1
3
1 2
2 1
3 4
样例输出1
1
样例解释1
把第一张牌翻过来，那么就有两个2一个3朝上了，2的数量超过了半数。
样例输入2
3
1 2
3 4
5 6
样例输出2
Impossible
样例解释2
所有数字都只有一个，因此相同的数字数超过半数是不可能的。
最多只有四种数的个数会超过n/2，
所有数先排序，然后枚举，当一个数的个数为n/2时，就用这个数来更新答案
注意：如果正反都为同一个数，这个数只能算1个
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 300001 int a[N],b[N],c[N<<]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
int n,cnt=;
read(n);
for(int i=;i<=n;++i)
{
read(a[i]); c[++cnt]=a[i];
read(b[i]); if(a[i]!=b[i]) c[++cnt]=b[i];
}
sort(c+,c+cnt+);
int ans=n+,sum=,m=n+>>;
for(int i=;i<=cnt;++i)
{
if(c[i]==c[i-])
{
++sum;
if(sum==m)
{
int tot=;
for(int j=;j<=n;++j) if(a[j]==c[i]) tot++;
tot=min(tot,m);
ans=min(ans,m-tot);
}
}
else sum=;
}
if(ans>n) printf("Impossible");
else printf("%d",ans);
}
2. 后缀数组
题目描述
给定一个字符串S，它的长为n，后缀数组的功能是，将其所有后缀按字典序从小到大排好序。我们对其做一点小小的改动：再给定一个数字m，记ssi表示从S的第i位开始、长度最多为m的子串，我们希望将这些字符串{ssi}按字典序从小到大排序。举个栗子，当S="abcab"，m=2时，ssi的值分别为：
ss1="ab"
ss2="bc"
ss3="ca"
ss4="ab"
ss5="b"
但是，只是把{ssi}全部排好序还是太简单了。初始状态下，ss1~ssn按顺序排成一行，我们只能通过不断交换某两个相邻字符串的位置来做排序。再举个栗子，把上面提到的ss1~ss5排好序的一种方案是：
(0) 原序列："ab", "bc", "ca", "ab", "b"
(1) 交换第3和第4个串："ab", "bc", "ab", ca", "b"
(2) 交换第2和第3个串："ab", "ab", "bc", ca", "b"
(3) 交换第4和第5个串："ab", "ab", "bc", b", "ca"
(4) 交换第3和第4个串："ab", "ab", "b", bc", "ca"
现在，你需要求出，最少通过多少次相邻字符串交换，才能把所有子串{ssi}排成字典序从小到大的形式。
( ´_ゝ｀)NOIP怎么可能会考后缀数组
输入格式
第一行包含两个整数n和m；
第二行包含字符串S，它的长为n，只包含小写字母。
输出格式
一个整数，表示最少交换次数。
样例输入
5 2
abcab
样例输出
4
样例解释
样例就是题目描述中提到的例子。
数据范围
对于20%的数据，有n≤10;
对于40%的数据，有n≤100;
对于60%的数据，有n≤5000;
另有10%的数据，有m≤5;
另有10%的数据，S是随机生成的;
对于100%的数据，有1≤m≤n≤50000
把所有子串排好序，答案就是逆序对的个数
注意处理相同子串
唯一的问题是如何对所有子串排序
正解思路：
哈希排序
即归并排序字符串，用二分+哈希值找出两个字符串第一个不同的字母
#include<cstdio>
#include<iostream> #define N 50001 const int mod=; int n,m,d; char s[N]; long long has[N],bit[N]; int a[N],b[N]; long long ans; int GetHash(int l,int r)
{
int tmp;
if(r<=n)
{
tmp=has[r]-has[l-]*bit[r-l+]%mod;
if(tmp<) tmp+=mod;
}
else
{
tmp=has[n]-has[l-]*bit[n-l+]%mod;
if(tmp<) tmp+=mod;
tmp=1LL*bit[r-n]%mod;
}
return tmp;
} int cmp(int i,int j)
{
int l=,r=m,mid,tmp=-;
while(l<=r)
{
mid=l+r>>;
if(GetHash(i,i+mid-)!=GetHash(j,j+mid-)) tmp=mid,r=mid-;
else l=mid+;
}
if(tmp==-) return ;
char x= i+tmp->n ? ' ' : s[i+tmp-];
char y= j+tmp->n ? ' ' : s[j+tmp-];
if(x<y) return -;
return ;
} void gbsort(int l,int r)
{
if(l==r) return;
int mid=l+r>>;
gbsort(l,mid);
gbsort(mid+,r);
int i=l,j=mid+,k=l;
while(i<=mid && j<=r)
{
d=cmp(a[i],a[j]);
if(d<=) b[k++]=a[i++];
else if(d>) b[k++]=a[j++],ans+=mid-i+;
}
//printf("%d %d %I64d\n",l,r,ans);
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(k=l;k<=r;++k) a[k]=b[k];
} int main()
{
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
scanf("%d%d",&n,&m);
scanf("%s",s+);
bit[]=;
for(int i=;i<=n;++i) bit[i]=bit[i-]*%mod;
has[]=s[]-'a'+;
for(int i=;i<=n;++i) has[i]=(has[i-]*+(s[i]-'a'+))%mod;
for(int i=;i<=n;++i) a[i]=i;
gbsort(,n);
std::cout<<ans;
}
考场思路：
假设当前比较每个子串的第i位
把第i位为a的放到一个vector里，b放到一个vector里……
继续递归下去
时间复杂度 O（n^2 * 26)
那个26 可以去掉，但 每一层递归都要开26的vector，实测 更慢
不用vector 会MLE
50分代码
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define lowbit(x) x&-x using namespace std; int n,m,cnt; #define N 50002 char s[N]; int rank[N],sum[N]; int c[N]; void mysort(int dep,vector<int>v)
{
int siz=v.size();
if(!siz) return;
if(dep==m)
{
for(int i=;i<siz;i++)
rank[v[i]]=cnt+;
cnt++;
return;
}
vector<int>b;
int mi=,mx=-;
for(int i=;i<siz;i++)
{
if(v[i]+dep==n+) rank[v[i]]=++cnt;
else mi=min(mi,s[v[i]+dep]-'a'),mx=max(mx,s[v[i]+dep]-'a');
}
for(int i=mi;i<=mx;i++)
{
b.clear();
for(int j=;j<siz;j++)
if(v[j]+dep<=n && s[v[j]+dep]-'a'==i) b.push_back(v[j]);
mysort(dep+,b);
}
} void add(int x)
{
while(x<=cnt)
{
c[x]++;
x+=lowbit(x);
}
} int query(int x)
{
int tot=;
while(x)
{
tot+=c[x];
x-=lowbit(x);
}
return tot;
} int main()
{
// freopen("sort.in","r",stdin);
// freopen("sort.out","w",stdout);
scanf("%d%d",&n,&m);
scanf("%s",s+);
vector<int>ve;
for(int i=;i<=n;i++) ve.push_back(i);
mysort(,ve);
for(int i=;i<=n;i++) sum[rank[i]+]++;
for(int i=;i<=n;i++) sum[i]+=sum[i-];
//for(int i=1;i<=n;i++) printf("%d ",rank[i]);
//printf("\n");
//for(int i=1;i<=cnt;i++) printf("%d ",sum[i]);
//printf("\n");
long long ans=;
for(int i=;i<=n;i++)
{
ans+= rank[i]== ? sum[rank[i]] : sum[rank[i]]-query(rank[i]-);
add(rank[i]);
}
cout<<ans;
}
3. 巧克力
题目描述
有一块分成n*m个格子的矩形巧克力，虽然形状上很规整但质量分布并不均匀，每一格有各自的重量，用n*m个正整数表示。你需要将这一整块巧克力切成k小块，要求每块都是矩形，且它们的重量分别为a1~ak。一块巧克力的重量等于它包含的所有格子的重量之和。
切巧克力的时候，你可以每次选一块大的巧克力，沿着某条格线横向或纵向将其切成两块小的巧克力。切下来的小块巧克力可以继续切割。切割路线不能是折线或斜线。任何时候当前的所有巧克力块都必须是矩形的。
对于给定的巧克力和分割要求，请你判断是否存在一个切割方案满足上述要求。
输入格式
输入包含多组测试数据。输入文件的第一行包含一个正整数T，表示数据组数；
接下来，每组测试数据的第一行包含3个正整数n, m, k，表示巧克力的长、宽以及它需要被切成多少块；
接下来n行，每行m个正整数，第i行第j个数wi,j表示巧克力第i行第j列那一格的重量；
接下来一行包含k个正整数a1~ak，表示要求切成的每块巧克力的重量。
输出格式
输出T行，表示对每组测试数据的判断结果。如果第i组测试数据存在一种切割方案，则在第i行输出"yes"，否则输出"no"。
样例输入
2
3 3 4
1 2 3
4 5 6
7 8 9
12 16 8 9
2 2 2
1 1
1 1
1 3
样例输出
yes
no
状压
50%的数据每个格子的w=1
f[i][j][s] 表示用 状态为s的巧克力 能否拼出 i*j的的矩形
记忆化搜索 枚举横切、竖切
根据面积计算新的长宽
100%的数据待填
20暴力
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; int T,n,m,k; int w[][],a[]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void init()
{
read(n); read(m); read(k);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
read(w[i][j]);
for(int i=;i<=k;i++) read(a[i]);
} namespace solve1
{
int pos[],tot[]; bool ok; void judge()
{
memset(tot,,sizeof(tot));
for(int i=;i<=k-;i++)
for(int j=pos[i-]+;j<=pos[i];j++)
tot[i]+=w[][j];
for(int j=pos[k-]+;j<=m;j++) tot[k]+=w[][j];
sort(tot+,tot+k+);
for(int i=;i<=k;i++)
if(tot[i]!=a[i]) return;
ok=true;
} void dfs(int sum,int last)
{
if(ok) return;
if(sum==k) { judge(); return; }
for(int i=last+;i+k--sum<m;i++)
{
if(sum== && i==)
{
int esa=;
}
pos[sum]=i;
dfs(sum+,i);
if(ok) return;
}
} void work()
{
sort(a+,a+k+);
ok=false;
dfs(,);
puts(ok ? "yes" : "no");
}
} namespace solve2
{
void work()
{
int sum=;
for(int i=;i<=k;i++) sum+=a[i];
if(sum>n*m) puts("no");
else puts("yes");
}
} int main()
{
freopen("chocolate.in","r",stdin);
freopen("chocolate.out","w",stdout);
read(T);
while(T--)
{
init();
if(n==) solve1::work();
else solve2::work();
}
}