“范式杯”2023牛客暑期多校训练营1

D：Chocolate

大意：给定一个n*m的方格，上面摆放着巧克力，k和w在玩一个游戏，规定k先行，在每个回合内玩家可以吃掉坐标(x,y)内所有的巧克力(i<=x&&j<=y)，在他们回合内至少吃掉一块巧克力，谁最后吃巧克力谁就输了，问赢家是谁

做法：一个很经典的博弈论，chomp游戏，这个游戏经过证明可以得到先手必赢，放在题目中只有一块巧克力的时候是后手赢

code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<vector>
 7 #include<stack>
 8 #include<bitset>
 9 #include<cstdlib>
10 #include<cmath>
11 #include<set>
12 #include<list>
13 #include<deque>
14 #include<map>
15 #include<queue>
16 #include <iomanip>
17 #include<ctime>
18 using namespace std;
19 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
20 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
21 #define int long long 
22 #define double long double
23 #define endl '\n'
24 #define inf LLONG_MAX
25 #define iinf INT_MAX
26 typedef pair<int,int> PII;
27 const double PI = acos(-1.0);
28 const double eps = 1e-6;
29 const int INF = 0x3f3f3f3f;
30 const int N = 1e9;
31 int n,m;
32 signed main()
33 {
34     IOS;
35     cin>>n>>m;
36     if(n==1&&m==1)
37     {
38         cout<<"Walk Alone"<<endl;
39     }
40     else
41     {
42         cout<<"Kelin"<<endl;
43     }
44     return 0;
45 }

J:

做法：

我们的目的是在n的基础上赢得m元，那题目给定了如果赢一把的话就可以赢一元

我们可以忽略掉前面的输赢，对于本金x来讲我们考虑最多输的局数为r

在满足2^r-1<=x的前提下连续输的概率是(1/2)^r，赢的概率则相反

对于上述的r，对应都有x的例如当r=1时，x=1，r=2时，x=3，那么在[1,2],这个所处的范围，我们赢的概率是相同的，都是1/2

那么由此可以推得，我们的x在一段确定的区间中的概率相同，而我们最终所求的概率即为所有概率相乘。

 code:

 1 // 我们的目的是在n的基础上赢得m元，那题目给定了如果赢一把的话就可以赢一元
 2 // 我们可以忽略掉前面的输赢，对于本金x来讲我们考虑最多输的局数为r
 3 // 在满足2^r-1<=x的前提下连续输的概率是(1/2)^r，赢的概率则相反
 4 // 对于上述的r，对应都有x的例如当r=1时，x=1，r=2时，x=3，那么在[1,2],这个所处的范围，我们赢的概率是相同的，都是1/2
 5 // 那么由此可以推得，我们的x在一段确定的区间中的概率相同，而我们最终所求的概率即为所有概率相乘。
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<algorithm>
 9 #include<iostream>
10 #include<string>
11 #include<vector>
12 #include<stack>
13 #include<bitset>
14 #include<cstdlib>
15 #include<cmath>
16 #include<set>
17 #include<list>
18 #include<deque>
19 #include<map>
20 #include<queue>
21 #include <iomanip>
22 #include<ctime>
23 using namespace std;
24 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
25 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
26 #define int long long 
27 #define double long double
28 #define endl '\n'
29 #define inf LLONG_MAX
30 #define iinf INT_MAX
31 typedef pair<int,int> PII;
32 const double PI = acos(-1.0);
33 const double eps = 1e-6;
34 const int INF = 0x3f3f3f3f;
35 const int mod = 998244353;
36 int n,m;
37 int quick_power(int a, int k)  // 求a^k mod p
38 {
39     int res = 1 % mod;
40     while (k)
41     {
42         if (k & 1) res = res * a % mod;
43         a = a * a % mod;
44         k >>= 1;
45     }
46     return res;
47 }
48 int inv(int x)//求逆元
49 {
50     return quick_power(x,mod-2);
51 }
52 signed main()
53 {
54     IOS;
55     cin>>n>>m;
56     int ans=1;
57     for(int i=n;i<n+m;)//枚举本金
58     {
59         int r=log2(i+1);//最多输的局数
60         int ed=min(n+m,(1ll<<(r+1))-1);//终点,起点是i
61         //out<<(1ll<<(r+1))-1)<<endl;
62         int len=ed-i;//区间长度
63         int p=(1-inv(quick_power(2,r))+mod)%mod;//最多能赢的概率
64         ans=ans*quick_power(p,len);//去区间长度的概率进行相乘就是连续获胜x把的概率
65         ans=ans%mod;
66         i=ed;
67     }
68     cout<<ans<<endl;
69     return 0;
70 }

k:给定无向图，规定可以在任意一条边内插入一个点使得(u,v)->(u,w),(w,v)，问图中最多有多少个点和1的距离不超过k

做法：

尽量避免在靠近点1出分链

同时

1.若一个点u的周围的点v不是由当前点更新而来，那么对于u-v这条边我们可以一直加点，不会对后续产生影响。

2.若一个点u周围的点v为u的前驱节点，那么对于u-v这条路径我们不能够进行加点。

3.若当前点u无后继节点且d[u]<=k，那么我们同理也可以继续加点

总而言之，我们看当前是否能够进行加点的规则为：是否对周围节点产生影响。

Code:

  1 // 尽量避免在靠近点1出分链
  2 // 同时
  3 // 1.若一个点u的周围的点v不是由当前点更新而来，那么对于u-v这条边我们可以一直加点，不会对后续产生影响。
  4 // 2.若一个点u周围的点v为u的前驱节点，那么对于u-v这条路径我们不能够进行加点。
  5 // 3.若当前点u无后继节点且d[u]<=k，那么我们同理也可以继续加点
  6 // 总而言之，我们看当前是否能够进行加点的规则为：是否对周围节点产生影响。
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<algorithm>
 10 #include<iostream>
 11 #include<string>
 12 #include<vector>
 13 #include<stack>
 14 #include<bitset>
 15 #include<cstdlib>
 16 #include<cmath>
 17 #include<set>
 18 #include<list>
 19 #include<deque>
 20 #include<map>
 21 #include<queue>
 22 #include <iomanip>
 23 #include<ctime>
 24 using namespace std;
 25 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 26 #define TLE (double)clock()/CLOCKS_PER_SEC<=0.95
 27 #define int long long 
 28 #define double long double
 29 #define endl '\n'
 30 #define inf LLONG_MAX
 31 #define iinf INT_MAX
 32 typedef pair<int,int> PII;
 33 const double PI = acos(-1.0);
 34 const double eps = 1e-6;
 35 const int INF = 0x3f3f3f3f;
 36 const int N = 4e5+10;
 37 int n,m,k;
 38 vector<int>g[N];
 39 int dis[N];
 40 bool vis[N];
 41 int pre[N];
 42 void bfs(int x)
 43 {
 44     memset(dis,0x3f,sizeof dis);
 45     queue<int>q;
 46     dis[x]=0;
 47     vis[x]=true;
 48     q.push(x);
 49     while(!q.empty())
 50     {
 51         int u=q.front();
 52         q.pop();
 53         for(int i=0;i<g[u].size();i++)
 54         {
 55             int v=g[u][i];
 56             if(!vis[v])
 57             {
 58                 vis[v]=true;
 59                 dis[v]=dis[u]+1;
 60                 pre[v]=u;
 61                 q.push(v);
 62             }
 63         }
 64     }
 65 }
 66 signed main()
 67 {
 68     IOS;
 69     cin>>n>>m>>k;
 70     for(int i=1;i<=m;i++)
 71     {
 72         int u,v;
 73         cin>>u>>v;
 74         g[u].push_back(v);
 75         g[v].push_back(u);
 76     }
 77     for(int i=1;i<=n;i++)
 78     {
 79         pre[i]=i;
 80     }
 81     bfs(1);
 82     int ans=0;
 83     for(int i=1;i<=n;i++)//满足条件的可以直接加入
 84     {
 85         if(dis[i]<=k)
 86         {
 87             ans++;
 88         }
 89     }
 90     for(int i=2;i<=n;i++)
 91     {
 92         if(g[i].size()==1)//没有后继
 93         {
 94             ans+=max(k-dis[i],0ll);
 95         }
 96         for(int j=0;j<g[i].size();j++)
 97         {
 98             int v=g[i][j];
 99             if(pre[v]!=i&&pre[i]!=v)//既不是前驱也不是后继
100             {
101                 ans+=max(k-dis[i],0ll);
102             }
103         }
104     }
105     cout<<ans<<endl;
106     return 0;
107 }