- Prob.1 2015 神奇的幻方
模拟就好了。
（这不是noip2017的初赛题么。）代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a[55][55];
int n,x,y,cnt;
int main(){
scanf("%d",&n);
x=1; y=n/2+1;
while(cnt<n*n){
a[x][y]=++cnt;
if((x==1&&y==n)||a[x-1][y+1]) x++;
else{
if(x==1) x=n,y++;
else if(y==n) x--,y=1;
else x--,y++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<n;j++)
printf("%d ",a[i][j]);
printf("%d\n",a[i][n]);
}
return 0;
}
- Prob.2 2015 信息传递
（这个题真是有毒）
先把入度为0的点依次去掉，bfs实现，
最后图中剩下一个简单环或者多个简单环。
然后对这些环跑dfs，求出最小的那个环长
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 200005
using namespace std;
int dis[MAXN],to[MAXN],in[MAXN],vis[MAXN];
int n,st,ans=0x3f3f3f3f;
queue<int>q;
void dfs(int u,int fa){
dis[u]=dis[fa]+1; vis[u]=1;
if(vis[to[u]]) ans=min(ans,dis[u]-dis[to[u]]+1);
else dfs(to[u],u);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&to[i]),in[to[i]]++;
for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
while(!q.empty()){
int u=q.front(); q.pop(); vis[u]=1;
in[to[u]]--; if(!in[to[u]]) q.push(to[u]);
}
for(int i=1;i<=n;i++) if(!vis[i]){
dfs(i,0);
}
printf("%d",ans);
return 0;
}
- Prob.3 2015 斗地主
（令人畏惧的题目）
思路：
dfs用来出顺子牌，
然后剩下的牌按照贪心策略去出，使得出牌次数尽量少。
吐槽：这个搜索还真是暴力。贪心也很666。
然后具体看代码实现。
（但是Vijos上的第95组怎么过不了？？？试了几个网上的代码，似乎也不行。）
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 25
using namespace std;
int a[MAXN];
int T,n,ans;
int get(){//贪心打出非顺子牌
static int cnt,c[MAXN];
memset(c,0,sizeof(c)); cnt=0;
for(int i=0;i<=13;i++) c[a[i]]++;
while(c[4]&&c[2]>1) cnt++,c[4]--,c[2]-=2;
while(c[4]&&c[1]>1) cnt++,c[4]--,c[1]-=2;
while(c[4]&&c[2]) cnt++,c[4]--,c[2]--;
while(c[3]&&c[2]) cnt++,c[3]--,c[2]--;
while(c[3]&&c[1]) cnt++,c[3]--,c[1]--;
cnt+=c[1]+c[2]+c[3]+c[4];
return cnt;
}
void dfs(int now){//dfs顺子牌
if(now>=ans) return;
int tmp=get();
ans=min(now+tmp,ans);
for(int i=2,j;i<=13;i++){//三顺子
j=i;
while(a[j]>=3) j++;
if(j-i>=2){
for(int p=i+1;p<j;p++){
for(int k=i;k<=p;k++) a[k]-=3;
dfs(now+1);
for(int k=i;k<=p;k++) a[k]+=3;
} }
}
for(int i=2,j;i<=13;i++){//二顺子
j=i;
while(a[j]>=2) j++;
if(j-i>=3){
for(int p=i+2;p<j;p++){
for(int k=i;k<=p;k++) a[k]-=2;
dfs(now+1);
for(int k=i;k<=p;k++) a[k]+=2;
}
}
}
for(int i=2,j;i<=13;i++){//单顺子
j=i;
while(a[j]>=1) j++;
if(j-i>=5){
for(int p=i+4;p<j;p++){
for(int k=i;k<=p;k++) a[k]-=1;
dfs(now+1);
for(int k=i;k<=p;k++) a[k]+=1;
}
}
}
}
int main(){
scanf("%d%d",&T,&n);
while(T--){
memset(a,0,sizeof(a)); ans=0x3f3f3f3f;
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
if(x==1) x=13;
else if(x!=0)x--;
a[x]++;
}
dfs(0);
printf("%d\n",ans);
}
return 0;
}
- Prob.4 2015 跳石头
二分
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a[50005];
int n,m,len;
bool check(int lim){
int p=0,cnt=0;
for(int i=1;i<=n+1;i++){
if(a[i]-a[p]>=lim) p=i;
else{
cnt++;
if(i==n+1&&p==0) return 0;
if(cnt>m) return 0;
}
}
return 1;
}
int binary(int l,int r){
int mid,ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main(){
scanf("%d%d%d",&len,&n,&m); a[n+1]=len;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=binary(0,len);
printf("%d",ans);
return 0;
}
- Prob.5 2015 子串
dp[i][j][k][0/1]: 匹配到A串的i位置，B串的j位置，且已经选了k段，i位置选不选 的方案数
转移就看代码吧，很明显的。
（怎么我的方法和网上的都不太一样？？？原来车车和我一样,==似乎本质和网上也差不多。呃，我在干嘛？）
#include<cstdio>
#include<cstring>
#include<iostream>
#define rint register int
using namespace std;
const int mod=1000000007;
char A[1005],B[205];
int dp[2][205][205][2];
int n,m,o,ans,x=1,y=0;
void add(int &a,int b){
a=(1ll*a+b)%mod;
}
int main(){
scanf("%d%d%d",&n,&m,&o);
scanf("%s%s",A+1,B+1);
dp[0][0][0][0]=1;
for(rint i=0;i<=n;i++){
swap(x,y);
memset(dp[y],0,sizeof(dp[y]));
for(rint j=0;j<=min(i,m);j++)
for(rint k=0;k<=min(j,o);k++){
add(dp[y][j][k][0],dp[x][j][k][0]);
add(dp[y][j][k][0],dp[x][j][k][1]); if(A[i+1]==B[j+1]) add(dp[y][j+1][k+1][1],dp[x][j][k][0]),
add(dp[y][j+1][k+1][1],dp[x][j][k][1]),
add(dp[y][j+1][k][1],dp[x][j][k][1]);
}
}
add(ans,dp[y][m][o][0]),add(ans,dp[y][m][o][1]);
printf("%d",ans);
return 0;
}
- Prob.6 2015 运输计划
好题,二分答案。
统计一个cnt，表示有多少个计划不能在时限内完成。
同时记下最大的md，表示耗时最长的那个计划与二分的mid的差值。
然后在树上打上差分标记。
跑一遍dfs，对于一条被所以超时的计划经过的边，如果其边权大于等于md，则合法。（要把权值下放到点）
如果不存在这样的边，则不合法。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 300005
#define rint register int
using namespace std;
struct express{
int s,t,lca,len;
}p[MAXN];
struct edge{
int to,val,next;
}e1[MAXN*2],e2[MAXN*2];
int head1[MAXN],head2[MAXN],fa[MAXN],dis[MAXN],c[MAXN];
int n,m,ent1=2,ent2=2,cnt,md;
bool fg;
inline void add(int u,int v,int w,int &ent,int *head,edge *e){
e[ent]=(edge){v,w,head[u]};
head[u]=ent++;
}
inline int find(int u){
return u==fa[u]?u:fa[u]=find(fa[u]);
}
inline void Tarjan(int u,int dad,int val){ //Tarjan求lca
fa[u]=u; dis[u]=dis[dad]+val;
for(rint i=head2[u];i;i=e2[i].next){
int v=e2[i].to,j=e2[i].val;
if(!fa[v]) continue;
p[j].lca=find(v);
p[j].len=dis[u]+dis[v]-2*dis[p[j].lca];
}
for(rint i=head1[u];i;i=e1[i].next){
int v=e1[i].to;
if(v==dad) continue;
Tarjan(v,u,e1[i].val);
}
fa[u]=dad;
}
inline int dfs(int u,int dad,int val){
int tmp=0;
for(rint i=head1[u];i;i=e1[i].next){
int v=e1[i].to;
if(v==dad) continue;
tmp+=dfs(v,u,e1[i].val);
}
tmp+=c[u];
if(tmp==cnt&&val>=md) fg=1;
return tmp;
}
inline bool check(int lim){
cnt=0; md=0;
memset(c,0,sizeof(c));
for(rint i=1;i<=m;i++){
if(p[i].len>lim) {
cnt++;
md=max(md,p[i].len-lim);
c[p[i].s]++; c[p[i].t]++;
c[p[i].lca]-=2;
}
}
fg=0;
dfs(1,0,0);
return fg;
}
inline int binary(int r){//二分答案，（最小时间）
int l=0,mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int main(){
scanf("%d%d",&n,&m); int r=0;
for(rint i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,ent1,head1,e1);
add(v,u,w,ent1,head1,e1);
r+=w;
}
for(rint i=1;i<=m;i++){
scanf("%d%d",&p[i].s,&p[i].t);
add(p[i].s,p[i].t,i,ent2,head2,e2);
add(p[i].t,p[i].s,i,ent2,head2,e2);
}
Tarjan(1,0,0);
int ans=binary(r);
printf("%d",ans);
return 0;
}