[noip][2017]

Day1T1

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;
}

Day1T2

思路

虽然这个题就是模拟，但是坑点还是比较多的，如果不好好读题目就很容易炸掉。首先，对于初始变量大于终止变量的不能进入循环。如果初始变量和终止变量都是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;
}

Day1T3

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;
}

Day2T1

思路

先\(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;
}

Day2T2

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;
}

Day2T3

思路

还是只会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;
}