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 }