题目链接：https://loj.ac/problems/search?keyword=NOIP2014
暴力
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
const int p[][5]={{0,-1,1,1,-1},
{1,0,-1,1,-1},
{-1,1,0,-1,1},
{-1,-1,1,0,1},
{1,1,-1,-1,0}};
int n,n1,n2,a[10100],b[10100];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
n=read();n1=read();n2=read();
rep(i,0,n1-1) a[i]=read();
rep(i,0,n2-1) b[i]=read();
int ans1=0,ans2=0;
rep(i,0,n-1)
{
int na=a[i%n1],nb=b[i%n2];
if (p[na][nb]==1) ans1++;
else if (p[na][nb]) ans2++;
}
printf("%d %d",ans1,ans2);
return 0;
}
暴力
dfs这棵树的时候统计以当前节点为中间节点的点对的答案
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 10007
#define eps 1e-8
struct node{int to,nxt;}sq[400400];
int all=0,head[200200];
int n,a[200200];
ll ans=0,maxans=0;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void add(int u,int v)
{
all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}
void dfs(int u,int fu)
{
int sum=a[fu];
int mx1=a[fu],mx2=0;
for (int i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v==fu) continue;
dfs(v,u);
ans=(ans+sum*a[v]%maxd)%maxd;
sum=(sum+a[v])%maxd;
if (a[v]>mx1) {mx2=mx1;mx1=a[v];}
else if (a[v]>mx2) mx2=a[v];
}
maxans=max(maxans,1ll*mx1*mx2);
}
int main()
{
n=read();
rep(i,1,n-1)
{
int u=read(),v=read();
add(u,v);add(v,u);
}
rep(i,1,n) a[i]=read();
dfs(1,0);
ans=ans*2%maxd;
printf("%lld %lld",maxans,ans);
return 0;
}记\(f[i][j]\)表示在\((i,j)\)的时候所需要的最小点击数，那么首先可以用类似背包的方式处理\(x,y\)。接下来还有两个小细节：
（1）对于那些跑出了上边界的情况，我们可以将第二维开大一些，之后把那些超出去的部分全部记在\(f[i][m]\)，根据定义这显然是可行的
（2）对于水管直接赋为\(inf\)，防止下一次转移被使用
之后就比较简单了
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,m,k,u[100100],d[10010],x[10010],y[10010],dp[10010][2010];
int vis[10010];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
n=read();m=read();k=read();
rep(i,1,n)
{
x[i]=read();y[i]=read();
d[i]=1;u[i]=m;
}
d[0]=1;u[0]=m;
rep(i,1,k)
{
int pos=read();
d[pos]=read()+1;u[pos]=read()-1;vis[pos]=1;
}
memset(dp,0x3f,sizeof(dp));
rep(i,1,m)
if ((i>=d[0]) && (i<=u[0])) dp[0][i]=0;
rep(i,1,n)
{
rep(j,x[i]+1,m+x[i])
{
dp[i][j]=min(dp[i-1][j-x[i]]+1,dp[i][j-x[i]]+1);
if (j>m) dp[i][m]=min(dp[i][m],dp[i][j]);
}
rep(j,1,m-y[i])
dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]);
rep(j,1,d[i]-1) dp[i][j]=maxd;
rep(j,u[i]+1,m) dp[i][j]=maxd;
}
int ans=maxd;
rep(i,1,m) ans=min(ans,dp[n][i]);
if (ans<maxd) printf("1\n%d",ans);
else
{
per(i,n-1,0)
{
rep(j,1,m)
{
if (dp[i][j]<maxd)
{
int ans=0;
rep(k,0,i) ans+=vis[k];
printf("0\n%d",ans);
return 0;
}
}
}
}
return 0;
}暴力
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n=0,m=0,k,d,a[310][310];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
d=read();k=read();
rep(i,1,k)
{
int x=read(),y=read();
n=max(x,n);m=max(y,m);
a[x][y]=read();
}
int ans=0,cnt=0;
rep(i,0,n) rep(j,0,m)
{
int sum=0;
rep(p,max(0,i-d),min(n,i+d))
rep(q,max(0,j-d),min(m,j+d))
sum+=a[p][q];
if (ans<sum) {ans=sum;cnt=0;}
if (ans==sum) cnt++;
}
printf("%d %d",cnt,ans);
return 0;
}第一遍bfs倒着做，找到所有可以用的点
第二遍bfs正着做，求答案
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{int to,nxt;}sq[200200],sq1[200200];
int all=0,all1=0,head[10010],head1[10010];
int n,m,dis[10010],ok[10010],vis[10010],st,ed;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void add(int u,int v)
{
all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}
void add1(int u,int v)
{
all1++;sq1[all1].to=v;sq1[all1].nxt=head1[u];head1[u]=all1;
}
void bfs1()
{
queue<int> q;
q.push(ed);vis[ed]=1;
while (!q.empty())
{
int u=q.front();q.pop();
for (int i=head1[u];i;i=sq1[i].nxt)
{
int v=sq1[i].to;
if (!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
int bfs2()
{
queue<int> q;
memset(dis,0x3f,sizeof(dis));
q.push(st);dis[st]=0;
while (!q.empty())
{
int u=q.front();q.pop();
for (int i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if ((ok[v]) && (dis[v]>=maxd))
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
if (dis[ed]>=maxd) return -1;
else return dis[ed];
}
int main()
{
n=read();m=read();
rep(i,1,m)
{
int u=read(),v=read();
add(u,v);add1(v,u);
}
st=read();ed=read();
bfs1();
rep(u,1,n)
{
ok[u]=1;
for (int i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (!vis[v]) ok[u]=0;
}
}
int ans=bfs2();
printf("%d",ans);
return 0;
}枚举答案，hash判断合法
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,m;
ll a[110];
vector<int> ans;
ll read()
{
ll x=0;int f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=(x*10+(ch-'0'))%maxd;ch=getchar();}
return (x*f+maxd)%maxd;
}
int main()
{
scanf("%d %d",&n,&m);
rep(i,0,n) a[i]=read();
//rep(i,0,n) cout << a[i] << " ";cout << endl;
rep(i,1,m)
{
ll powe=1,sum=0;
rep(j,0,n)
{
sum=(sum+powe*a[j])%maxd;
powe=powe*i%maxd;
}
if (!sum) ans.pb(i);
}
int len=ans.size();
printf("%d\n",len);
rep(i,0,len-1) printf("%d\n",ans[i]);
return 0;
}原文：https://www.cnblogs.com/encodetalker/p/11749807.html