2019.8.1_牛客博客

Police Stations

https://cn.vjudge.net/problem/CodeForces-796D

思路见

巧妙的bfs题，利用了bfs最短路的性质

代码实现的时候也有很多坑。

访问过的顶点显然要开vis数组，

坑1：边也要开vis数组，因为最短路的边肯定不能删，删过的边也不能重复计入答案

坑2：见代码49行。加入d的限制反而WA了。其实不用加上距离d的限制。因为本来就可行，而bfs找到是最短路，同一连通块的距离是不会超过d的

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define maxn (300000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,k,d;
int loc[maxn];
bool vis[maxn];
bool vise[maxn];
queue<pair<int,int> >Q;
int head[maxn],to[maxn<<1],pre[maxn<<1],tot,id[maxn<<1],fa[maxn];
void adde(int u,int v,int i)
{
    to[++tot]=v,pre[tot]=head[u],head[u]=tot,id[tot]=i;
}
int ans[maxn],num;
int main()
{
    RD3(n,k,d);for(int i=0;i<k;i++)RD1(loc[i]);
    sort(loc,loc+k);
    k=unique(loc,loc+k)-loc;
    for(int i=0;i<n;i++){Q.push(pair<int,int>(loc[i],0));vis[loc[i]]=1;}
    for(int i=1;i<n;i++)
    {
        int u,v;RD2(u,v);adde(u,v,i),adde(v,u,i);
    }
    while(!Q.empty())
    {
        pair<int,int>p=Q.front();Q.pop();
        int u=p.first,dis=p.second;
       // if(dis==d)continue;
        for(int i=head[u];i;i=pre[i])
        {
            int v=to[i],e=id[i];if(fa[u]==v)continue;
            if(vis[v])
            {
                if(!vise[e])
                {
                    vise[e]=1;
                    ans[num++]=e;
                }
                continue;
            }
            vis[v]=1;vise[e]=1;fa[v]=u;
            Q.push(pair<int,int>(v,dis+1));
        }
    }
    printf("%d\n",num);
    for(int i=0;i<num;i++)printf("%d ",ans[i]);
    return 0;
}

Number Transformation II

https://cn.vjudge.net/problem/CodeForces-346C

比较玄学的暴力题

一开始想用dp，结果TLE

官方粗略证明：

设dp[i]是a转移到i的最小步数。

$dp[i]=min(dp[j]+1),i<j<=a$

dp[i]是单调的

因此直接贪心，每次减去最大的，一旦b==a了就break

坑：不得不优化的地方

如果

$( a-a\%c<b) ,a'<a$

那么

$a'-a'\%c<b$

所以暴力的过程中把没用的x_i去掉，不然又会TLE

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,x[maxn],a,b,sz;
int main()
{
    RD1(n);for(int i=0;i<n;i++)RD1(x[i]);
    RD2(a,b);if(a==b){printf("0");return 0;}
    sort(x,x+n);sz=unique(x,x+n)-x;
    //for(int i=0;i<sz;i++)see(x[i]),NL;
    int ans=0;
    while(a>b)
    {
        int tmp=a-1;
        for(int i=0;i<sz;i++)
        {
            if(a-a%x[i]>=b)tmp=min(tmp,a-a%x[i]);
        }
        a=tmp,ans++;
        if(a==b)break;
        while(sz&&a-a%x[sz-1]<b)sz--;
    }
    printf("%d",ans);
    return 0;
}

Border

https://cn.vjudge.net/problem/CodeForces-1010C

巧妙的数论问题

坑：每种a_i数量是无限的，而且0总是合法的，一个都不选

思路：

根据定理，(a1,a2,a3,,,,an)可以表示的数的集合是g=gcd(a1,a2,a3......an)及其倍数

答案就是集合

$(g*0,g*1,g*2.............g*(k-1),g*(k),g*(k+1)....)\%k$

g*k开始%k就重复了

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,k,a[maxn];
set<int>S;
int main()
{
    RD2(n,k);
    int rt;RD1(rt);
    for(int i=1;i<n;i++){int t;RD1(t);t%=k;rt=__gcd(t,rt);}
    for(int i=0;i<k;i++)S.insert(i*rt%k);
    printf("%d\n",S.size());
    for(set<int>::iterator it=S.begin();it!=S.end();it++)
    {
        printf("%d ",*it);
    }
    return 0;
}