[洛谷 P2679]子串
DP神题……
第一眼都能看出来是DP，然后大约构思就出来了，但细节很复杂啊……
看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态，但是注意[tex]A[i]=B[j][/tex]（字符数组细节此处未予考虑）的情况和整体情况要独立对待，否则这题只能233
然后下面就不难想了。但是注意直接开数组会233，要开滚动数组防MLE。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
register int i,j,p,now,pre;
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",A,B);
d[0][0][0][1]=1;
for(i=1;i<=n;i++){
now=i%2;
pre=1-now;
d[now][0][0][1]=1;
for(j=1;j<=m;j++){
if(A[i-1]==B[j-1])
for(p=1;p<=min(k,j);p++){
d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
}
else
for(p=1;p<=min(k,j);p++){
d[now][j][p][0]=0;
d[now][j][p][1]=d[pre][j][p][1];
}
}
}
printf("%d\n",d[n%2][m][k][1]);
return 0;
}
[CF 705C]Thor
这题我考试的时候想出各种蜜汁数据结构。
但是正解是：暴力！
好了好了，暴力也是要优化的。首先给消息编号，然后用一个bitset记下来哪个删了哪个没删，这个都能想到。
不过接下来有个挺头疼的问题：操作3阅读的信息可能在操作2中会被再次阅读，如此一来效率就很低了……咋整？
注意大消息队列里的消息编号肯定是升序的，每个程序的消息队列的编号也是升序的，所以说大队列中同一程序的消息的编号和该程序自身队列中的消息编号的顺序是一致的。如此一来，在操作3中可以顺便把程序队列中的消息也删掉，效率大为提升。
代码：
#include <cstdio>
#include <queue>
#include <utility>
#include <cctype>
#include <bitset>
using namespace std;
const int maxn=300001;
typedef pair<int,int> pii;
bitset<maxn> vis;
queue<int> S[maxn];
queue<pii> Q;
// I/O优化
inline int readint(){
char c=getchar();
register int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int bf[10];
inline void writeint(int x){
register int p=0;
if(x==0){
bf[p++]=0;
}else{
while(x){
bf[p++]=x%10;
x/=10;
}
}
for(register int i=p-1;i>=0;i--)
putchar('0'+bf[i]);
}
int main(){
register int ans=0,cnt=0;
register int temp,temp_2,q,u,v;
int n;
n=readint();
q=readint();
while(q--){
u=readint();
v=readint();
if(u==1){
cnt++;
S[v].push(cnt);
Q.push(make_pair(v,cnt));
ans++;
}else{
if(u==2){
while(!S[v].empty()){
temp=S[v].front();
S[v].pop();
if(!vis[temp]){
vis[temp]=true;
ans--;
}
}
}else{
while(!Q.empty() && (temp=Q.front().second)<=v){
temp=Q.front().second;
temp_2=Q.front().first;
Q.pop();
if(!vis[temp]){
vis[temp]=true;
S[temp_2].pop();
ans--;
}
}
}
}
writeint(ans);
putchar('\n');
}
return 0;
}
[BZOJ 1715]虫洞
呜……这题现在才A
这道题就是给一个图让判断有没有负环，没什么难度
然后……我写邻接表竟然开小内存了……
尽管如此我感觉我写此题时的代码风格还是不错的，比较值得学习
代码：
/**************************************************************
Problem: 1715
User: danihao123
Language: C++
Result: Accepted
Time:92 ms
Memory:920 kb
****************************************************************/
#include <cstdio>
#include <queue>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn=501,maxm=5201;
namespace Graph{
int n;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int tot=0;
inline void AddEdge(int u,int v,int d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
inline void ClearGraph(){
memset(first,0,sizeof(first));
memset(next,0,sizeof(next));
memset(to,0,sizeof(to));
memset(dist,0,sizeof(dist));
tot=0;
}
int cnt[maxn];
bool inQueue[maxn];
int d[maxn];
bool SPFA(){
register int i,u;
queue<int> Q;
memset(cnt,0,sizeof(cnt));
memset(inQueue,0,sizeof(inQueue));
for(i=1;i<=n;i++){
d[i]=0;
cnt[i]=1;
inQueue[i]=true;
Q.push(i);
}
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=first[u];i;i=next[i]){
if(d[to[i]]>d[u]+dist[i]){
d[to[i]]=d[u]+dist[i];
if(!inQueue[to[i]]){
Q.push(to[i]);
inQueue[to[i]]=true;
if(++cnt[to[i]]>n)
return true;
}
}
}
}
return false;
}
};
inline int readint(){
register char c;
register int temp=0;
c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
temp=temp*10+c-'0';
c=getchar();
}
return temp;
}
int main(){
register int i,m,w,u,v,d;
int F;
F=readint();
while(F--){
Graph::n=readint();
m=readint();
w=readint();
Graph::ClearGraph();
for(i=1;i<=m;i++){
u=readint();
v=readint();
d=readint();
Graph::AddEdge(u,v,d);
Graph::AddEdge(v,u,d);
}
for(i=1;i<=w;i++){
u=readint();
v=readint();
d=readint();
Graph::AddEdge(u,v,-d);
}
if(Graph::SPFA())
puts("YES");
else
puts("NO");
}
return 0;
}
[CodeVS 1012]最大公约数和最小公倍数问题
很经典的问题了吧……然而现在才A……
应注意[tex]P*Q=x*y[/tex]，然而[tex]P[/tex]和[tex]Q[/tex]都可表示为[tex]x[/tex]的乘积，问题就好思考多了。答案就是[tex]y/x[/tex]的质因子的子集数（同一种质因子不能同时分配到P与Q中，否则gcd(P,Q)会不等于x）。
注意有可能无解！
代码：
#include <iostream>
using namespace std;
inline int fj(int x){
register int i,ans=0;
for(i=2;i<=x && x>1;i++)
if(!(x%i)){
ans++;
while(!(x%i))
x/=i;
}
return ans;
}
int main(){
int a,b;
register int ans;
cin>>a>>b;
if(b%a)
ans=0;
else
ans=a==1?1:1<<fj(b/a);
cout<<ans<<endl;
return 0;
}
[BZOJ 3725]Matryca
很有意思的思考题。
这道题通过特殊情况我们可以猜想，假设最近两个不同色块距离为[tex]x[/tex]（这是半闭半开序列长度），则答案为[tex]n-x+1[/tex]。然而事实就是如此。
代码：
/**************************************************************
Problem: 3725
User: danihao123
Language: C++
Result: Accepted
Time:216 ms
Memory:1796 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000001;
char buf[maxn];
int main(){
int n;
register int i,now;
char last_s=0;
scanf("%s",buf);
n=strlen(buf);
register int ans=n;
for(i=0;i<n;i++){
if(buf[i]!='*'){
if(last_s){
if(buf[i]!=last_s){
ans=min(ans,i-now);
last_s=buf[i];
now=i;
}else{
now=i;
}
}else{
last_s=buf[i];
now=i;
}
}
}
printf("%d\n",n-ans+1);
return 0;
}
[BZOJ 4325]斗地主
是的你没有看错！就是这道坑提！
这题基本是个半成品，歧义真的，真的，真的很大。
至于方法？我们注意到同样的牌能一起出就尽可能避免拆开。例如，四带二分成炸弹加两单点（对子）肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解，并据此进行深度限制，再考虑出顺子。
然后，DFS暴搜即可。
顺便讲一下坑点：
- 顺子可以有A。
- 三带一，三带二，四代二都可以有头。但是大小头要区别开。
代码：
/**************************************************************
Problem: 4325
User: danihao123
Language: C++
Result: Accepted
Time:24 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
if(x>ans)
return;
int i,j,rest=0;
memset(cnt,0,sizeof(cnt));
for(i=0;i<=14;i++){
cnt[hand[i]]++;
}
while(cnt[4]>0){
cnt[4]--;
rest++;
if(cnt[2]>=2)
cnt[2]-=2;
else
if(cnt[1]>=2)
cnt[1]-=2;
}
while(cnt[3]>0){
cnt[3]--;
rest++;
if(cnt[2]>0)
cnt[2]--;
else
if(cnt[1]>0)
cnt[1]--;
}
if(hand[0] && hand[1] && cnt[1]>=2)
rest--;
ans=min(ans,cnt[1]+cnt[2]+rest+x);
for(i=3;i<=10;i++){
for(j=i;j<=14 && hand[j];j++){
hand[j]--;
if(j-i+1>=5)
dfs(x+1);
}
while(j>i)
hand[--j]++;
}
for(i=3;i<=12;i++){
for(j=i;j<=14 && hand[j]>=2;j++){
hand[j]-=2;
if(j-i+1>=3)
dfs(x+1);
}
while(j>i)
hand[--j]+=2;
}
for(i=3;i<=13;i++){
for(j=i;j<=14 && hand[j]>=3;j++){
hand[j]-=3;
if(j-i+1>=2)
dfs(x+1);
}
while(j>i)
hand[--j]+=3;
}
}
int main(){
int T,u,v;
register int i;
scanf("%d%d",&T,&n);
while(T--){
ans=n;
memset(hand,0,sizeof(hand));
for(i=1;i<=n;i++){
scanf("%d%d",&u,&v);
if(!u){
if(v==2)
hand[1]++;
else
hand[0]++;
}else{
if(u==1)
hand[14]++;
else
hand[u]++;
}
}
dfs(0);
printf("%d\n",ans);
}
return 0;
}
[CF 676B]Pyramid of Glasses
这题可以直接模拟，貌似也可过。但复杂度很高。
我们可以直接把t个单位的酒放入第一个杯，然后向下溢出，以此类推，这样复杂度就很优秀了。
代码：
#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
int i,ans=0;
long double temp;
if(x>n)
return 0;
for(i=1;i<=n;i++){
if(k[x][i]>=1.0){
ans++;
if(k[x][i]>1.0 && x<n){
temp=(k[x][i]-1.0)/2;
k[x][i]=1.0;
k[x+1][i]+=temp;
k[x+1][i+1]+=temp;
}
}
}
return ans+call(x+1);
}
int main(){
cin>>n>>k[1][1];
cout<<call(1)<<endl;
return 0;
}
[BZOJ 4152]The Captain
这题初看有些棘手。但是毕竟是最短路，[tex]min(abs(x_{1}-x_{2}),abs(y_{1}-y_{2}))[/tex]这样的边，大可以分成两条边来建，于是乎min就形同虚设了。并且我们可以看到这样建图有一个好处：跨越若干点的方案可以一定可以分成图上的若干边。问题大为简化，迎刃而解。
但这提有个丧病的地方：卡SPFA。加了一些优化照样挂。所以我一气之下写了可并堆优化的Dijkstra :)当然可并堆用的是pb_ds辣。
代码：
/**************************************************************
Problem: 4152
User: danihao123
Language: C++
Result: Accepted
Time:4888 ms
Memory:17412 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <cctype>
#include <bitset>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
const int maxn=200001;
int n;
inline int abs(int x){
return x<0?-x:x;
}
int first[maxn];
int next[maxn*4],to[maxn*4],dist[maxn*4];
int graph_cnt=0;
inline void Add_Edge(int x,int y,int d){
graph_cnt++;
next[graph_cnt]=first[x];
first[x]=graph_cnt;
to[graph_cnt]=y;
dist[graph_cnt]=d;
}
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef __gnu_pbds::priority_queue<my_pair,greater<my_pair> > Heap;
Heap::point_iterator ite[maxn];
Heap Q;
int dij(){
register int i,u;
memset(d,0x7f,sizeof(d));
d[1]=0;
ite[1]=Q.push(make_pair(0,1));
while(!Q.empty()){
u=Q.top().second;
Q.pop();
if(vis[u])
continue;
vis[u]=true;
for(i=first[u];i;i=next[i]){
if(d[to[i]]>(dist[i]+d[u])){
d[to[i]]=dist[i]+d[u];
if(ite[to[i]]!=0)
Q.modify(ite[to[i]],make_pair(d[to[i]],to[i]));
else
ite[to[i]]=Q.push(make_pair(d[to[i]],to[i]));
}
}
}
return d[n];
}
int pr[maxn][2];
int order1[maxn],order2[maxn];
int cmp1(const int i,const int j){
return pr[i][0]<pr[j][0];
}
int cmp2(const int i,const int j){
return pr[i][1]<pr[j][1];
}
// I/O优化
inline int readint(){
char c=getchar();
register int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int main(){
register int i;
n=readint();
for(i=1;i<=n;i++){
pr[i][0]=readint();
pr[i][1]=readint();
order1[i]=i;
order2[i]=i;
}
sort(order1+1,order1+1+n,cmp1);
sort(order2+1,order2+1+n,cmp2);
for(i=1;i<=n;i++){
if(i!=1){
Add_Edge(order1[i],order1[i-1],pr[order1[i]][0]-pr[order1[i-1]][0]);
Add_Edge(order2[i],order2[i-1],pr[order2[i]][1]-pr[order2[i-1]][1]);
}
if(i!=n){
Add_Edge(order1[i],order1[i+1],pr[order1[i+1]][0]-pr[order1[i]][0]);
Add_Edge(order2[i],order2[i+1],pr[order2[i+1]][1]-pr[order2[i]][1]);
}
}
printf("%d\n",dij());
return 0;
}
[BZOJ 1756]小白逛公园
这题是很经典的线段树题。
我们可以发现最长子序列或跨越中点，或不跨越中点。若不跨越则肯定在左子或右子中，跨越则是左子最大后缀和和右子最大前缀和之和。问题便迎刃而解。（当然，求区间最大前缀/后缀和要用上区间和）
需注意此题可能会出现a>b！
代码：
/**************************************************************
Problem: 1756
User: danihao123
Language: C++
Result: Accepted
Time:2604 ms
Memory:49648 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001;
struct Node{
int L,R;
int maxP,maxS,ans,sum;
};
Node Tree[maxn*4];
int A[maxn];
void merge(Node& O,Node& LC,Node& RC){
O.sum=LC.sum+RC.sum;
O.maxP=max(LC.maxP,LC.sum+RC.maxP);
O.maxS=max(RC.maxS,RC.sum+LC.maxS);
O.ans=max(max(LC.ans,RC.ans),LC.maxS+RC.maxP);
}
void maintain(int o){
Node& O=Tree[o],LC=Tree[o<<1],RC=Tree[o<<1|1];
merge(O,LC,RC);
}
void build_tree(int o,int L,int R){
Node& O=Tree[o];
O.L=L;
O.R=R;
if(L==R){
O.maxP=O.maxS=O.ans=O.sum=A[L];
}else{
int M=L+(R-L)/2;
build_tree(o<<1,L,M);
build_tree(o<<1|1,M+1,R);
maintain(o);
}
}
void update(int o,int p,int v){
Node& O=Tree[o];
int& L=O.L,R=O.R;
if(L==R){
O.maxP=O.maxS=O.ans=O.sum=v;
}else{
int M=L+(R-L)/2;
if(p<=M)
update(o<<1,p,v);
else
update(o<<1|1,p,v);
maintain(o);
}
}
int ql,qr;
Node query(int o){
Node& O=Tree[o];
int& L=O.L,R=O.R;
if(ql<=L && R<=qr){
return Tree[o];
}
int M=L+(R-L)/2;
Node ANS,LC,RC;
if(ql<=M){
LC=query(o<<1);
if(qr>M){
RC=query(o<<1|1);
merge(ANS,LC,RC);
return ANS;
}else{
return LC;
}
}else{
RC=query(o<<1|1);
return RC;
}
}
int main(){
int n,m;
register int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&A[i]);
build_tree(1,1,n);
int k,a,b;
Node ans;
for(i=1;i<=m;i++){
scanf("%d%d%d",&k,&a,&b);
if(k&1){
if(a>b)
swap(a,b);
ql=a;
qr=b;
ans=query(1);
printf("%d\n",ans.ans);
}else{
update(1,a,b);
}
}
return 0;
}
[BZOJ 2429]聪明的猴子
图论填坑中……
这题不难，直接造图搞MST（严格讲是最小瓶颈生成树）即可。比较感人的是，Kruskal竟然也能过……
代码：
/**************************************************************
Problem: 2429
User: danihao123
Language: C++
Result: Accepted
Time:320 ms
Memory:12592 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1001,maxm=501;
int n;
struct Edge{
int u,v,d;
bool operator < (const Edge& x) const{
return d<x.d;
}
};
// DJoinst Set
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
for(register int i=1;i<=n;i++)
p[i]=i;
// memset(rank,0,sizeof(rank));
}
// Kruskal
int m=0;
Edge E[maxn*maxn];
int MST(){
register int i,ans,count=0;
init_set();
sort(E,E+m);
for(i=0;i<m && count<=(n-1);i++){
if(!is_same(E[i].u,E[i].v)){
union_set(E[i].u,E[i].v);
ans=E[i].d;
count++;
}
}
return ans;
}
int MK[maxm],Tree[maxn][2];
int main(){
int monkey;
register int i,j,sd,ans=0;
scanf("%d",&monkey);
for(i=1;i<=monkey;i++)
scanf("%d",&MK[i]);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&Tree[i][0],&Tree[i][1]);
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
E[m].u=i;
E[m].v=j;
E[m].d=hypot(abs(Tree[i][0]-Tree[j][0]),abs(Tree[i][1]-Tree[j][1]));
m++;
}
}
sd=MST();
for(i=1;i<=monkey;i++)
if(MK[i]>=sd)
ans++;
printf("%d\n",ans);
return 0;
}
