河南萌新2024第五场
A 日历游戏
题目大意：
alice，bob玩游戏，给定一个2000.1.1到2024.8.1之间的任意一个日期，每次进行一次操作（保证合法日期）
天数+1，例如2000.1.1 -> 2000.1.2
月份+1，例如2000.1.1 -> 2000.2.1
alice先手，问有没有必胜策略
思路：
标准的博弈问题，不看年份，如果想要alice最后变到8.1，那么alice可以通过7.31获胜，或者7.1
对于每个月一号而言，如果alice想获胜，那么必须是从奇数月份开始改，才可以保证最后是8月（偶数）
对于每个月最后一天而言，如果想要alice获胜，alice先手可以改为下个月1号，但必须保证改完后这个月是偶数
常规月份最后一天
1.31 奇数月份最后一天alice先手，可直接获胜，前面天数相隔完整的一轮（2的整数倍），29，27，可以递推改到1.31奇数月份最后一天，但是1.30如果可以改到上输，
2.28 *偶数月份最后一天，不可以改天数，需要改到下个月3.28，第一种b改到3.29，属于3.31的完整轮次，奇数轮最后一天赢，第二种b改到4.28，属于4月30的完整轮次，赢
2.29 *偶数月份最后一天，不可以改天数，需要改到下个月3.29，导致是3.31的完整轮次，输
3.31 奇数月份最后一天alice先手，可直接获胜
4.30 偶数月份最后一天，需要改到下个月5.30，b改到5.31，奇数月份最后一天
5.31 奇数月份最后一天alice先手，可直接获胜
6.30 偶数月份最后一天，需要改到下个月7.30，b改到7.31，奇数月份最后一天
7.31 奇数月份最后一天alice先手，可直接获胜
8.31 偶数月份最后一天，需要改到下个月9.1，奇数月份第一天
//9.30 奇数月份最后一天alice先手，可直接获胜
10.31 偶数月份最后一天，需要改到下个月11.1，奇数月份第一天
//11.30 奇数月份最后一天alice先手，可直接获胜
12.31 偶数月份最后一天，可改到下个月1.1，奇数月份第一天，或者1.31奇数月份最后一天
因此可以看出想要得出月份+天数=奇数的8.1，必须保证先手是月份+天数的日期，但是9.30和11.30两个可以转入10.30和12.30，这两个需要特判为赢，其余月份+天数为偶数的赢，否则输
Solved：
void solve()
{int a,b,c;cin>>a>>b>>c;int f=0;if (b==9&&c==30) f=1;if (b==11&&c==30) f=1;if ((b+c)%2==0) f=1;if (f==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}
I 小美想打音游
赛时没过是因为要用abs，看了眼数据范围，把longlong关了，赛后发现不能关
K- 小美想游泳
题目大意：
在一个图中，从a点到b点，找到一条路中，所有边中最大边权最小的路径
思路：
可以用Dijkstra算法实现
- 如果不是找最短路，而是让这条路中的边权最大值最小化，那么可以将边存为无向图，就是将边存2次
- 该题的松弛操作应为 当前点的边权 > (上一个点的边权，该点的边权) ，就更换，换句话说，只选择边权小的路走，不考虑总共走多少条路
Solved：
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se secondusing namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;//邻接表
int h[N],e[N],w[N],ne[N],idx;int dist[N];//存储最短路径
int st[N];//确定是否最短
int n,m;
int a,b;
//图的加边
void add(int x,int y,int z){e[idx]=y,w[idx]=z;ne[idx]=h[x];h[x]=idx++;
}void Dijkstra()
{//初始化distmemset(dist,0x3f,sizeof(dist));dist[a]=0;//堆优化Dijkstra//first:距离 second:节点编号priority_queue<PII,vector<PII>,greater<PII>> q;q.push({0,a});while(!q.empty()){auto t=q.top();q.pop();//ver:点编号 dis:距离int ver=t.se,dis=t.fi;
// if(st[ver]) continue;
// st[ver]=1;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];//j:下个点编号if(dist[j]>max(dist[ver],w[i])){dist[j]=max(dist[ver],w[i]);q.push({dist[j],j});}}}
}signed main()
{//初始化邻接表memset(h,-1,sizeof(h));cin>>n>>m;while(m--){int x,y,z;cin>>x>>y>>z;add(x,y,z);add(y,x,z);}cin>>a>>b;Dijkstra();cout<<dist[b];return 0;
}
H 区间问题2
st表模板题，后续单独出一篇st表
需要注意该题输入量比较大，需要优化输入，直接用给定数组把st表初始化
for(int i=1;i<=n;i++){cin>>f[i][0];}
#include <bits/stdc++.h>
#define int long longusing namespace std;const int N=1e6+10;
int a[N];
int f[N][20];//st表
int n;void init()
{for(int j=1;j<=20;j++){//循环长度for(int i=1;i+(1<<j)-1<=n;i++){//i~i+1<<(j-1) -1, i+1<<(j-1) +1 ~i+1<<j;f[i][j]=max(f[i][j-1],f[i+ (1<<j-1) ][j-1]);}}
}int query(int l,int r)
{int len=r-l+1;int k=log2(len);//求长度小于len的最大2的整次幂//l~l+1<<k , r-(1<<k) +1~rreturn max(f[l][k],f[r-(1<<k)+1][k]);
}signed main()
{std::ios::sync_with_stdio(0);cin.tie(0);cout.tie();cin>>n;for(int i=1;i<=n;i++){cin>>f[i][0];}init();int m;cin>>m;while(m--){int l,r;cin>>l>>r;cout<<query(l,r)<<"\n";}return 0;
}