多做，视野才开阔，不要老是想着水题！
P7800 [COCI2015-2016#6] PAROVI
题目分析
一来可以直接暴力求解，硬性枚举是否选择这些线段，显然必须优化。
我们先预处理每个二元组，很明显我们要将二元组按照右端点来排序。
可以利用dp来优化，我们设\(f[i][j]\)为选择前\(i\)条线段，覆盖了\([1,j]\)区间的方案数。
当\(l_{i+1}≤j\) 时，选则就会有\([1,r_{i+1}]\)，否则仍然是 \([1,j]\)。
而当 \(l_{i+1}>j\)，必然有一段区间没有覆盖，并且转移到\(f[i][j]\)。
代码如下
点击查看代码
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll f[405][405];
int n,cnt,ans;
int const mod=1000000000;
inline ll re(){
ll k=0,f=1ll;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
f=-1ll;
ch=getchar();
}
while(isdigit(ch)){
k=k*10ll+(ch^48ll);
ch=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
putchar('-');
x=~x+1;
}
if(x>9)
wr(x/10ll);
putchar(x%10+48ll);
}
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
struct node{
int a,b;
}p[405];
signed main(){
n=re();
for(int i=1;i<=n;++i){
for(int j=1;j<i;++j){
if(gcd(i,j)==1){
p[cnt].a=j,p[cnt].b=i;
++cnt;
}
}
}
f[0][p[0].b]=1;
f[0][1]=1;
for(int i=0;i<cnt-1;++i){
for(int j=1;j<=n;++j){
f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
if(p[i+1].a<=j)
f[i+1][p[i+1].b]=(f[i+1][p[i+1].b]+f[i][j])%mod;
else
f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
}
}
wr(f[cnt-1][n]);
return 0;
}
P7859 [COCI2015-2016#2] GEPPETTO
题目分析
把不合法材料的转化为一个状态，后面枚举材料选择的状态（即\(2^n\)种）即可。
结论：大水题
点击查看代码
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int n,m;
ll ans;
inline ll re(){
ll k=0,f=1ll;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
f=-1ll;
ch=getchar();
}
while(isdigit(ch)){
k=k*10ll+(ch^48ll);
ch=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
putchar('-');
x=~x+1;
}
if(x>9)
wr(x/10ll);
putchar(x%10+48ll);
}
struct node{
int x,y;
}a[405];
signed main(){
n=re(),m=re();
for(int i=1;i<=m;++i){
a[i].x=re();
a[i].y=re();
}
for(int i=0;i<(1<<n);++i){
bool f=0;
for(int j=1;j<=m;++j){
if((i&(1<<a[j].x-1))&&(i&(1<<a[j].y-1))){
f=1;
break;
}
}
if(!f)
++ans;
}
wr(ans);
return 0;
}
P7861 [COCI2015-2016#2] SAVEZ
题目分析
见到最长子序列就应该想到dp，对于此题目的方程有：\(f[i]=\max\{f[j]\}+1\)（\(j<i\wedge x_j\)为\(x_i\)的前缀以及后缀）。
问题转为如何判断一个字符串是另一个字符串的前后缀。
我们可以将字符串集合\(\{s_1,s_2...s_n\}\)前后合为一个二元组，也就是有\((s_1,s_n),(s_2,s_{n-1})...(s_n,s_1)\)，所以只用判断\(x_j\)组成的二元组是否为\(x_i\)的二元组的前缀即可。
如何存储？利用trie，所以将每个二元组当成字符集达到\(26^2\)的字符串输入进去，在插入的过程中，如果到达了一个字符串末尾，我们就进行dp操作，插入完之后记录该字符串编号。
而这个trie的每一条边，两个端点的两个字符a和b，可以转化成为一个数：\((\)a\(-\)'A'\()\)\(\times Base\)+\((\)b\(-\)'A'\()\)，最后利用map/unordered_map实现动态开点。
代码实现
点击查看代码
#include <map>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int n,len;
int ans,idx;
int f[2000005],id[2000005];
char s[2000005];
map< int,map<int,int> > trie;
inline ll re(){
ll k=0,f=1ll;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
f=-1ll;
ch=getchar();
}
while(isdigit(ch)){
k=k*10ll+(ch^48ll);
ch=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
putchar('-');
x=~x+1;
}
if(x>9)
wr(x/10ll);
putchar(x%10+48ll);
}
signed main(){
n=re();
for(int i=1;i<=n;++i){
scanf("%s",s+1);
len=strlen(s+1);
int x=0,has;
for(int j=1;j<=len;++j){
f[i]=max(f[i],f[id[x]]+1);
has=(s[j]-'A')*26+(s[len-j+1]-'A');
if(trie[x].find(has)==trie[x].end())
trie[x][has]=++idx;
x=trie[x][has];
}
if(id[x])
f[i]=max(f[i],f[id[x]]+1);
ans=max(ans,f[i]);
id[x]=i;
}
wr(ans);
return 0;
}
P7862 [COCI2015-2016#2] DRŽAVA
十分有营养的题目，以后多点这种题吧。
题目分析
因为要求最大的\(D\)的最小值，显然具有二分的性质。那么我们就可以贪心的将所有距离不超过\(D\)的两个城市连接起来，接着判断是否存在一个子县满足居民数总合可以被\(K\)整除。
爆搜？超时，所以考虑dp，不过dp的状态怎么设置？如何转移？
每次加入一个新点之前，一个县中总人数集合取模\(K\)的集合我们设为\(S_1=\{r_1,r_2...,r_m\}\)，再加入一个点\(i\)，它的权重为\(w_i\)，会多产生一个集合\(S_2=\{(r_1+w_i)\mod K,(r_2+w_i)\mod K,...(r_m+w_i)\mod K\}\)，最终整个县中可以产生的所有元素集合就是\(S_1\cup S_2\)。
所以我们就可以设置一个\(bool\)类型的状态\(f[i][j]\)来表示在第\(i\)个县是否可以组合出人数取模\(k\)后结果为\(j\)的总人数之和，每次新加入一个点，我们都可以在\(O(K)\)的时间内扫描一遍之后更新之，当然你不可以去动原数组，所以用另一个数组来代替之。
那么算法框架本身结束，接下来考虑优化。
直接建边空间开销极大，所以我们不妨先进行排序。首先扫描到一个点\((m,n)\)的时候，由于二点距离最大为\(D\)，所以我们的需要的另一个点的\(x\)坐标一定属于区间\([m-D,m+D]\)中，故根据\(x\)坐标排序，二分查找所需点即可。
似乎还是有些许麻烦，能不能再次优化？
我们来看这样的一个东西，如果我们选择\(K\)个自然数去组成可重集，一定会存在一个子集，它的元素和可以被\(K\)整除。如何得到的呢？我们来看，如果将这\(K\)个自然数随意的排成一个序列，然后每个位置\(i\)的求出前缀和取模\(K\)后的结果，记为\(sum[i]\)，如果存在两个位置\(i,j\)可以满足\(sum[i]-sum[j]=0\)（也就是说，二者相等），那么区间\([j+1,i]\)的和一定可以被\(K\)整除。介于最多\(k+1\)个取模后的前缀和，根据抽屉原理，一定存在两个位置\(i,j\)可以满足\(sum[i]-sum[j]=0\)。
所以事实上我们就可以只找距离点\((m,n)\)最近的\(k-1\)个点就行，排好序后从\(\max\{1,i-k+1\}\)中寻找\(k\)个点计算最大距离，得到这些最大距离中的最小值\(D\)，作为上界。
最后再想想我们真的可以直接连边吗？显然不能！不过还好根据我们之前二分的上界，超过上界的边就可以舍去不连接，剩下的先排序，再利用并查集维护即可。
代码如下
点击查看代码
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define eps 1e-5
using namespace std;
int n,K;
struct node{
double x,y;
int w;
}s[50005];
inline ll re(){
ll k=0,f=1ll;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
f=-1ll;
ch=getchar();
}
while(isdigit(ch)){
k=k*10ll+(ch^48ll);
ch=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
putchar('-');
x=~x+1;
}
if(x>9)
wr(x/10ll);
putchar(x%10+48ll);
}
struct Edge{
int u,v;
double dist;
}E[1500005];
int tote;
inline void add_edge(int u,int v,double d){
++tote;
E[tote].u=u,E[tote].v=v,E[tote].dist=d;
}
inline bool cmp_1(Edge a,Edge b){
return a.dist<b.dist;
}
int fa[50005];
inline int find_(int x){
return x==fa[x]?x:fa[x]=find_(fa[x]);
}
inline void merge(int x,int y){
x=find_(x);
y=find_(y);
fa[x]=y;
}
inline bool cmp(node a,node b){
return a.x<b.x;
}
inline double dis(double x_1,double x_2,double y_1,double y_2){
return sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2));
}
bool f_1[50005][35];
bool f_2[50005][35];
signed main(){
n=re(),K=re();
for(int i=1;i<=n;++i){
scanf("%lf%lf",&s[i].x,&s[i].y);
s[i].w=re();
s[i].w%=K;
}
sort(s+1,s+1+n,cmp);
double l=0,r=sqrt(2e16); //确定上下界，准备二分
for(int i=1;i<=n;++i){
double ans=0;
for(int j=max(1,i-K+1),cnt=1;cnt<=K;++j,++cnt) //对于每个固定好的点，我们只选择至多K条边
ans=max(ans,dis(s[i].x,s[j].x,s[i].y,s[j].y));
r=min(r,ans);
} //再次更新上界
for(int i=1;i<=n;++i){
for(int j=max(1,i-K+1),cnt=1;cnt<=K;++j,++cnt){
double dist=dis(s[i].x,s[j].x,s[i].y,s[j].y);
if(dist<=r) //排除在上界以外的
add_edge(i,j,dist);
}
}
sort(E+1,E+1+tote,cmp_1); //按照边权排序
while(r-l>eps){ //二分答案：求解D
double mid=(l+r)/2;
for(int i=1;i<=n;++i)
fa[i]=i;
for(int i=1;E[i].dist<=mid;++i) //超过上界的就不要
merge(E[i].u,E[i].v); //并查集合并
memset(f_1,0,sizeof(f_1));
bool fin=0;
for(int i=1;i<=n;++i){
f_1[find_(i)][0]=1;
for(int j=0;j<K;++j)
f_2[fa[i]][(j+s[i].w-1)%K+1]=f_1[fa[i]][j];
if(f_2[fa[i]][K]){
r=mid;
fin=1;
break;
}
for(int j=0;j<K;++j)
f_1[fa[i]][j]|=f_2[fa[i]][j];
}
if(!fin)
l=mid;
}
printf("%.3lf",l);
return 0;
}
杂
如果可以的话，请加倍努力，达到那种没有太多人敢想但是你敢的高度
标签：总结,ch,int,ll,1ll,20220922,测试,include,getchar From： https://www.cnblogs.com/WXDreemurr/p/16720978.html