【牛客练习赛61】4月10日贪心/dfs/最短路

https://ac.nowcoder.com/acm/contest/5026

还是好菜=.=.=
卡在B时间太长了，一直没找出自己思路哪里错误。。。以后比赛30分钟搞不出一道题直接跳过吧====

B 贪心

设操作次数是ans，从减一操作上来讲， $ans$ 必然等于 $n,m$ 两个数中的较大者；所以这道题贪心是去想怎么使得乘2的操作次数最少，~~我的错误思路是让n,m两者diff（判断和2的i次方之间关系）不断变小，实际上只要n,m下降到m=n/2即可~~
不妨设 $n>m$ ,最终的目的是让 $n和m$ 相等,换个说法就是让n不断的逼近m，能让m变大的方法只有乘2，所以贪心思路就是：

m一直乘2，直到m>n/2
两者一起减1直到m=n/2
此时将m*2，n=m

问题来了？
为什么不先减1而是先去乘2？
因为 $n-1/m-1 > n/m$ ，所以越早增加m，乘以2的次数才会越少。举个例子 3,9，本来只需要乘2次2，(3,9)->乘2(6,9)->减到(3,6)->乘2(6,6)；
如果先减, (3,9)->(1,7)->乘2(2,7)->乘2(4,7)【这个地方1逼近到7/2需要乘以2次2】->减到(3,6)->乘2(6,6),则乘了3次2.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define MYINTMAX 0x3f3f3f3f

signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        if (n == m){
            cout << n << endl;
            continue;
        }
        if (n > m) swap(n, m);
        int res = m;
        while (n <= m / 2){
            n *= 2, ++res;
        }
        if (n < m){
            res++;
        }
        cout << res << endl;
    }
}

C dfs

裸dfs暴力……等会再更新一版优化的

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define MYINTMAX 0x3f3f3f3f
//INTMAX 2147483648  1e9 longlong 1e18
#define MYLLONGMAX 9223372036854775807 
#define ENTER cout<<endl
#define SCANF freopen("1.in","r",stdin);
priority_queue<int, vector<int>, greater<int>> pq; //小顶堆
int na,nb,nc,nd;
int limit[4];
int ans=0;
int h[4]={0};
vector<vector<int>> route;
vector<int> rou(12,0);
void dfs(int dep){
    if(dep==12) {
        ans++;
        route.push_back(rou);
    }
    for(int i=0;i<4;i++){
        if(h[i]+1<=limit[i]){
            h[i]++;
            rou[dep]=i;
            //cout<<i;
            dfs(dep+1);
            h[i]--;
        } 
    }
}
vector<pair<int,int>> same;
signed main()
{
    cin>>limit[0]>>limit[1]>>limit[2]>>limit[3];
    int t;
    cin>>t;
    while(t--){
        int x,y;cin>>x;cin>>y;
        same.push_back(make_pair(x,y));
    }
    dfs(0);
    int len1=route.size();
    int len2=same.size();
    for(int i=0;i<len1;++i){
        for(int j=0;j<len2;++j){
            int x=same[j].first-1;int y=same[j].second-1;
            if(route[i][x]!=route[i][y]){
                ans--;break;
            }
        }
    }
    cout<<ans<<endl;
}

更新一版优化的，dfs整体思路不变；并查集判断是否属于两个题答案必须相同

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
int na,nb,nc,nd;
int limit[4];
int ans=0;
int h[4]={0};
vector<vector<int>> route;
vector<int> rou(12,0);
int parent[1005];int choose[13];
int find(int i)
{ 
    if (parent[i] != i)
        parent[i] = find(parent[i]);
    return parent[i];
}
void dfs(int dep){
    if(dep>12) {
        ans++;
        return;
    }
    for(int i=0;i<4;i++){
        if(a[i]>0 && (parent[x]==x || choose[parent[x]]==i)){
            choose[dep]=i;
            limit[i]--;
            rou[dep]=i;
            //cout<<i;
            dfs(dep+1);
            limit[i]++;
        } 
    }
}
signed main()
{
    cin>>limit[0]>>limit[1]>>limit[2]>>limit[3];
    for(int i=1;i<=12;++i){
        parent[i]=i;
    }
    int t;
    cin>>t;
    while(t--){
        int x,y;cin>>x;cin>>y;
        x = find(x);
        y = find(y);
        if(x!=y){
            if(i>j) swap(i,j);
            parent[j]=i;
        }
    }
    for(int i=1;i<=12;++i){
        find(i);
    }
    dfs(1);
    cout<<ans<<endl;
}

D 最短路

n个点m条边，反向某条边，问1->n最短路会不会变短。
维护点1到其他点的最短路数组 $dis1[]$
建反向图，维护点n其他点的最短路数组 $dis2[]$
假设反向 $(u,v)$ ,如果最短路变短只有一种可能：就是最短路经过了新加的这条路径 $1->v->u->n$ ；所以看 $dis1[v]+dis2[u]+w(u,v)<dis1[n]$ 看是否成立就可以。
关键是dis1[v] dis2[u]会不会因为u->v的反向发生变化影响到上面不等式？

如果改变 $(u->v)$ 是原最短路上的某个边， $1->v->u->n$ 相当于多走了u->v这条路（不可达为INF），必然为NO（dis1[v] dis2[u]必然变大）；
所以答案为YES的时候必然u->v不是原1->n最短路上的边，那么dis1[v] dis1[u]都不会变

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MYINTMAX 0x3f3f3f3f
#define N 100005
const int P=1000000007,MAXN=100005,MAXM=200005;
struct node
{
  int i;
  ll d;
  bool operator<(const node& y)const
  {
      return d>y.d;
  }
}t,t1;
int n,m,q,i,j,k,u[MAXM],v[MAXM],w[MAXM],h[MAXN],ne[MAXM],h1[MAXN],ne1[MAXM];
ll d0[MAXN],d1[MAXN];
priority_queue<node> H;
int main()
{
  cin>>n>>m;
  for(i=1;i<=m;i++)
  {
      cin>>u[i]>>v[i]>>w[i];
      ne[i]=h[u[i]];
      h[u[i]]=i;
      ne1[i]=h1[v[i]];//反向图
      h1[v[i]]=i;
  }
  memset(d0,127,sizeof(d0));
  d0[1]=0;t.i=1;t.d=0;
  H.push(t);
  while(!H.empty())
  {
      t=H.top();
      H.pop();
      for(i=h[t.i];i;i=ne[i])if(d0[v[i]]>t.d+w[i])
      {
          t1.i=v[i];t1.d=t.d+w[i];
          d0[v[i]]=t.d+w[i];
          H.push(t1);
      }
  }
  memset(d1,127,sizeof(d0));
  d1[t.i=n]=t.d=0;
  H.push(t);
  while(!H.empty())
  {
      t=H.top();
      H.pop();
      for(i=h1[t.i];i;i=ne1[i])if(d1[u[i]]>t.d+w[i])
      {
          d1[t1.i=u[i]]=t1.d=t.d+w[i];
          H.push(t1);
      }
  }
  cin>>q;
  while(q--)
  {
      cin>>i;
      if(d0[n]>d0[v[i]]+w[i]+d1[u[i]])puts("YES");
      else puts("NO");
  }
  return 0;
}

A 签到模拟题

签到题不多说了，模拟一轮就知道了

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define MYINTMAX 0x3f3f3f3f
#define MYLLONGMAX 9223372036854775807 
#define ENTER cout<<endl
#define SCANF freopen("1.in","r",stdin);
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int h, a, H, A;
        cin >> h >> a >> H >> A;
        int ans = 0;

        int acnt = H / a;
        if (H % a != 0)
            acnt++;
        int ev = A * (acnt - 1);
        if(ev==0) cout<<-1<<endl;
        else {
            ans = h / ev;
            if(h%ev!=0) ans++; 
            cout << ans - 1 << endl;
        }
    }
}