30分思路：
倒着枚举答案z，用扩展欧几里得求解，如果能找到两个非负整数x,y使得ax+by=z则继续枚举，直到无解为止
100分：
最适用与考场上的做法，根据30分思路打表找规律。
30分代码:
#include<cstdio>
#include<iostream>
using namespace std;
#define int long long
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;y=0;
return a;
}
int t=exgcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-a/b*y;
return t;
}
inline int cei(int x,int y)
{
return x%y==0?x/y:x/y+1;
}
main()
{
int n,m,x,y;
cin>>n>>m;
exgcd(n,m,x,y);
for(int i=10000000;i>1;--i)
{
int xx=x*i,yy=y*i;
if(xx>=0&&yy>=0)
continue;
if(xx<0&&yy>=0)
{
int z=cei(-xx,m);
if(yy-z*n<0)
{
printf("%lld",i);
return 0;
}
else continue;
}
if(yy<0&&xx>=0)
{
int z=cei(-yy,n);
if(xx-z*m<0)
{
printf("%lld",i);
return 0;
}
else continue;
}
}
return 0;
}
100分代码：
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
ll n,m;
cin>>n>>m;
cout<<n*m-n-m;
return 0;
}
思路
虽然这个题就是模拟，但是坑点还是比较多的，如果不好好读题目就很容易炸掉。首先，对于初始变量大于终止变量的不能进入循环。如果初始变量和终止变量都是n那么算作常数复杂度。ERR优先于NO。然后慢慢地一边打注释一边模拟就好了。
代码
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<cstring>
using namespace std;
int t;
string s;
map<char,int>ma;
int read(string c)
{
int x=0;
int len=c.size();
for(int i=0;i<len;++i)
{
if(!isdigit(c[i])) continue;
x=x*10+c[i]-'0';
}
return x;
}
int read1(char x[])
{
int b=0;
int len=strlen(x)-1;
for (int i = 0; i <=len ; ++i)
if(isdigit(x[i])) b=b*10+x[i]-'0';
return b;
}
char zhan[110];
char cc[3],c[3];
int pdn[110];
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&t);
while(t--)
{
int w=0,L,bz=1,njs=0,ansbz=0,nmax=0,pdjs=0,top=0,tcbz=-1;
ma.clear();
scanf("%d",&L);
cin>>s;
if(s=="O(1)")bz=0;//0表示O(1)复杂度，1表示n^w复杂度
else w=read(s);
while(L--)
{
cin>>c;
if(c[0]=='F')
{
cin>>c;
zhan[++top]=c[0];//记录变量
if(ma[c[0]]==1) //判断是不是重名
ansbz=1;//ansbz为1答案为'ERR'
ma[c[0]]=1;
cin>>c;
cin>>cc;
if(((cc[0]!='n'&&c[0]!='n'&&read1(cc)<read1(c))||(c[0]=='n'&&cc[0]!='n'))&&(tcbz==-1))
tcbz=pdjs;
if(cc[0]=='n'&&c[0]!='n')
{
pdn[++pdjs]=1;//1表示为n,2表示为1
if(tcbz==-1)
{
njs++;
nmax=max(nmax,njs);
if(bz==0&&ansbz!=1)
ansbz=2;//ansbz为2答案为'No'
}
}
else
pdn[++pdjs]=2;
}
else//循环结束
{
ma[zhan[top]]=0;//销毁变量
top--;
if(tcbz==-1)
{
if(pdn[pdjs]==1)//将复杂度减去
njs--;
}
pdjs--;//当前层数--
if(pdjs==tcbz) tcbz=-1;
}
}
if(top!=0) ansbz=1;
if(ansbz==1)
{
printf("ERR\n");
continue;
}
if(w!=nmax) ansbz=2;
if(ansbz==2)
{
printf("No\n");
continue;
}
printf("Yes\n");
}
return 0;
}
30分思路
对于所有k=0的情况就是找最短路的条数，只要再找最短路的时候加一个判断就行了
100分思路
首先明显是dp，设f[i][k]表示到第i个点，路线长度与最短路差的绝度值不超过k的方案数。那么对于一条边u->v转移方程就是f[v][k]+=f[u][dis[v]+k-w-dis[u]],但是必须要求u先被更新完了才能去更新v，拓扑排序又有环，所以考虑记忆化搜索，f(v,k)表示与上方数组相同的含义，只是这时的v变成了u，u变成了v。
30分代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
const int N=100000*5+100,M=200000*5+100;
typedef pair<int,int> pi;
typedef long long ll;
int T,dis[N],mod,in[N],n,m,K;
struct node
{
int v,nxt,w;
node()
{
v=0,nxt=0,w=0;
}
}e[N];
int ejs,head[N],vis[N];
int qq[N];
void add(int u,int v,int w)
{
e[++ejs].v=v;e[ejs].w=w;e[ejs].nxt=head[u];head[u]=ejs;
}
int ans[N];
priority_queue<pi,vector<pi>,greater<pi> > q;
void dijkstral()
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
while(!q.empty()) q.pop();
dis[1]=0;
q.push(make_pair(dis[1],1));
for(int i=1;i<=n;++i)
{
while(vis[q.top().second]==1&&!q.empty()) q.pop();
int u=q.top().second;
vis[u]=1;
ans[1]=0;
for(int j=head[u];j;j=e[j].nxt)
{
int v=e[j].v;
if(dis[v]>dis[u]+e[j].w)
{
dis[v]=dis[u]+e[j].w;
q.push(make_pair(dis[v],v));
ans[v]=1;
}
else if(dis[v]==dis[u]+e[j].w)
{
ans[v]+=ans[u];
}
}
}
}
ll f[N][55];
int main()
{
scanf("%d",&T);
while(T--)
{
ejs=0;
memset(ans,0,sizeof(ans));
memset(head,0,sizeof(head));
scanf("%d%d%d%d",&n,&m,&K,&mod);
for(int i=1;i<=m;++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
dijkstral();
cout<<ans[n]<<endl;
}
return 0;
}
100分代码
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int N=100100,M=200010;
int n,m,K,t,ejs,mod,flag;
int head[N],dis[N],vis[N];
int f[N][60],bz[N][60];
queue<int>q;
struct node{
int u,v,w,nxt;
}e[M];
void add(int u,int v,int w) {
e[++ejs].u=u;e[ejs].v=v;e[ejs].w=w;e[ejs].nxt=head[u];head[u]=ejs;
}
void spfa() {
while(!q.empty()) q.pop();
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
q.push(1);
while(!q.empty()) {
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w) {
dis[v]=dis[u]+e[i].w;
if(!vis[v]) {
q.push(v);
vis[v]=1;
}
}
}
}
}
int dfs(int u,int k) {
if(bz[u][k]==1||flag==1) return flag=1;
if(bz[u][k]==2) return f[u][k];
bz[u][k]=1;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
int w=k+dis[u]-dis[v]-e[i].w;
if(w>K||w<0) continue;
f[u][k]+=dfs(v,w);
f[u][k]%=mod;
}
bz[u][k]=2;
return f[u][k];
}
int main() {
scanf("%d",&t);
while(t--) {
ejs=0;
memset(head,0,sizeof(head));
scanf("%d%d%d%d",&n,&m,&K,&mod);
for(int i=1,x,y,z;i<=m;++i) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
spfa();
memset(head,0,sizeof(head));
for(int i=1;i<=m;++i) {
swap(e[i].v,e[i].u);
e[i].nxt=head[e[i].u];
head[e[i].u]=i;
}
memset(f,0,sizeof(f));
memset(bz,0,sizeof(bz));
flag=0;
f[1][0]=1;
int ans=0;
for(int i=0;i<=K;++i) {
ans+=dfs(n,i);
ans%=mod;
if(flag==1){
ans=-1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}
思路
先\(n^2\)连边，然后从底下开始bfs看能不能搜到上面。
代码
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1010;
double n,h,R;
int S,T;
queue<int>q;
struct poin {
double x,y,z;
}p[N];
inline int ab(double x) {
return x>=0?x:-x;
}
struct node {
int v,nxt;
}e[N*N];
int ejs,head[N],vis[N];
void add(int u,int v) {
e[++ejs].v=v;e[ejs].nxt=head[u];head[u]=ejs;
}
inline int check(int x,int y) {
return (p[x].x-p[y].x)*(p[x].x-p[y].x)+(p[x].y-p[y].y)*(p[x].y-p[y].y)+(p[x].z-p[y].z)*(p[x].z-p[y].z)<=R*R*4;
}
int bfs() {
while(!q.empty()) q.pop();
memset(vis,0,sizeof(vis));
q.push(S);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(!vis[v]) {
q.push(v);
vis[v]=1;
}
}
}
return vis[T];
}
int main() {
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--) {
ejs=0;
memset(head,0,sizeof(head));
cin>>n>>h>>R;
T=n+1,S=0;
for(int i=1;i<=n;++i) {
cin>>p[i].x>>p[i].y>>p[i].z;
if(ab(p[i].z)<=R) add(S,i);
if(ab(p[i].z-h)<=R) add(i,T);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(check(i,j)&&i!=j) add(i,j),add(j,i);
if(bfs())
printf("Yes\n");
else printf("No\n");
}
return 0;
}
40分思路
对于所有v相等的情况，只要floyd一遍找出最短路。然后枚举起始点找最小花费即可。
100分思路
100分可以状态压缩，但是还是看了一骗模拟退火的题解。就是在进行prim的过程中，随机的选次优点进行更新。然后多进行几遍找出最优方案即可。
40分代码
#include<cstdio>
#include<cstring>
#include<iostream>
const int N=30;
using namespace std;
int f[N][N];
int main() {
int n,m,Z;
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i)
f[i][i]=0;
for(int i=1;i<=m;++i) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
Z=z;
f[x][y]=f[y][x]=1;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(f[i][j]>f[i][k]+f[k][j])
f[i][j]=f[i][k]+f[k][j];
int anss=0x7fffffff;
for(int i=1;i<=n;++i) {
int ans=0;
for(int j=1;j<=n;++j)
ans+=f[i][j];
anss=min(anss,ans);
}
printf("%d",anss*Z);
return 0;
}
100分代码
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=20,INF=10000000;
int vis[N],a[N][N],dis[N];
int n,m;
struct node {
int u,v;
};
bool operator < (const node &x,const node &y) {
return dis[x.u]*a[x.u][x.v]>dis[y.u]*a[y.u][y.v];
}
priority_queue<node> q;
int prim(int S) {
int ans=0;
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
int js=0;
node ls[N*N];
node k;
dis[S]=1;
vis[S]=1;
while(!q.empty()) q.pop();
for(int i=1;i<=n;++i) {//先找到S可以更新的点
if(a[S][i]<INF){
node e;
e.u=S,e.v=i;
q.push(e);
}
}
for(int i=1;i<n;++i) {
k=q.top();q.pop();
while(!q.empty()&&(vis[k.v]||rand()%n<1)) {//找到要用来更新的边
if(!vis[k.v]) ls[++js]=k;
k=q.top();
q.pop();
}
vis[k.v]=1;
dis[k.v]=dis[k.u]+1;//更新v
//printf("%d\n",dis[k.u]);
ans+=dis[k.u]*a[k.u][k.v];//加入生成树
while(js)//将预存的边加入队列
q.push(ls[js--]);
for(int j=1;j<=n;++j) {
if(a[k.v][j]<INF&&!vis[j]) {//扩展更多的边
node e;
e.u=k.v;
e.v=j;
q.push(e);
}
}
}
return ans;
}
int main() {
srand(time(0));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=INF;
for(int i=1;i<=m;++i) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x][y]=a[y][x]=min(a[x][y],z);
}
int ans=INF;
for(int i=1;i<=1000;++i)
for(int j=1;j<=n;++j)
ans=min(ans,prim(j));
printf("%d",ans);
return 0;
}
思路
还是只会30分模拟思路。
30分代码
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1010;
int q,a[N][N],n,m;
inline void change(int x,int y) {
int tmp=a[x][y];
for(int i=y;i<m;++i)
a[x][i]=a[x][i+1];
for(int i=x;i<n;++i)
a[i][m]=a[i+1][m];
a[n][m]=tmp;
}
int main() {
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[i][j]=(i-1)*m+j;
while(q--) {
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",a[x][y]);
change(x,y);
}
return 0;
}
总结
noip2017题目比较难，但是暴力只要打满了分数还是可观的。day1的暴力分有30+100+30=160。day2有100+40+30=170。这就有330分了，即便day1t2写挂了只要能拿到30分，就还是能拿到一等奖的(260)。所以打好暴力很重要。。
京公网安备 11010502036488号