难度排序，前六题，难度签到~铜牌题
1. 签到
纯签到
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//using i128 = __int128_t;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;string p;cin>>p;int ans=0;for(int i=1;i<=n;i++){string s;cin>>s;if(s==p) ans=i;}if(ans) cout<<ans<<endl;else cout<<-1<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}
2. 密码
一共有 \(n\) 个方程，每个方程最多有 \(6\) 个答案，只需要对所有答案求交集即可，过程可以用 \(set\) 维护，只要 \(set\) 的大小减小到 \(1\)，即为找到答案，后面的方程可以跳过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//using i128 = __int128_t;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;set<int> st;bool f=0;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;if(f) continue;set<int> t;//1.ax+b=cint x=(c-b)/a;if(a*x+b==c && x>=0) t.insert(x);//2.ax+c=bx=(b-c)/a;if(a*x+c==b && x>=0) t.insert(x);//3.bx+a=cx=(c-a)/b;if(b*x+a==c && x>=0) t.insert(x);//4.bx+c=ax=(a-c)/b;if(b*x+c==a && x>=0) t.insert(x);//5.cx+b=ax=(a-b)/c;if(c*x+b==a && x>=0) t.insert(x);//6.cx+a=bx=(b-a)/c;if(c*x+a==b && x>=0) t.insert(x);if(i==1) st=t;else{set<int> ans;for(auto val:t){if(st.count(val)) ans.insert(val);}st=ans;}if(st.size()==1){bool f=1;}}for(auto val:st){//此时st里只有一个元素cout<<val<<endl;}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}
3. 分配宝藏
考虑 \(n\) 比较小的情况
\(n=1\)：染染和船员的分配方案是：染染，0
因为此时只要染染自己投同意票，就可以通过，所以不需要给第 \(1\) 个船员分配
\(n=2\)：染染和船员的分配方案是：染染，0, 1
此时柒柒还需要一票，考虑最后一个人，如果柒柒的提案被否决，则情况就会变成 \(n=1\) 的方案，此时最后一个人只能获得0个。
所以柒柒只需要给最后一个人 1 个金币，就能获得他的一票
\(n=3:\)染染和船员的分配方案是：柒柒，0，1，0
‘此时柒柒还需要一票，对于倒数第二个人，如果柒柒的提案被否决，则情况就会变成 \(n=2\) 的方案，此时倒数第二个人只能获得0个。
所以柒柒只需要给倒数第二个人 1 个金币，就能获得他的一票
以此类推，对于 \(n\) 个船员的方案为，0，1，0，1，0，1，0，1
答案即为：\(2+4+6+8+....+n\) （ \(n\) 为偶数）或 \(2+4+6+8+....+(n-1)\)（ \(n\) 为奇数）
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//using i128 = __int128_t;
const ll inf = 1e18;
const int mod = 1e9+7;void solve(){int n;cin>>n;if(n==1){cout<<0<<endl;return;}if(n&1) n--;int ans=(2+n)*n/2/2%mod;cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}
4. 航线
其实是个最短路的板子题
对于每个格子，因为存在四个方向，所以只需要把每个格子 [n] [m] 拆成四个点 [n] [m] [0~3]
0~3分别代表右下左上四个方向
拆完点后，我们的初始点就是 [1] [0] [0] ，终点是[n] [m] [1]
然后直接跑 \(dijkstra\) 即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//using i128 = __int128_t;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,m;cin>>n>>m;vector<vector<int>> d(n+1,vector<int>(m+1));//转向费用vector<vector<int>> t(n+1,vector<int>(m+1));//路费for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>t[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>d[i][j];}}vector<vector<vector<int>>> dist(n+1,vector<vector<int>>(m+1,vector<int>(4,inf)));int dx[]={0,1,0,-1};//-> 0 下1 2<- 上3int dy[]={1,0,-1,0};dist[1][0][0]=0;auto dijkstra=[&]()->void {priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> q;q.push({0,1,0,0});//当前距离，x,y,方向while(q.size()){auto [w,x,y,dir]=q.top();q.pop();// cout<<x<<" "<<y<<" "<<w<<endl;int a=x+dx[dir],b=y+dy[dir];if(a<1 || a>n || b<1 || b>m) continue;for(int i=0;i<4;i++){if(dir!=i){if(w+d[a][b]+t[a][b]<dist[a][b][i]){dist[a][b][i]=w+d[a][b]+t[a][b];q.push({w+d[a][b]+t[a][b],a,b,i});}}else{if(w+t[a][b]<dist[a][b][i]){dist[a][b][i]=w+t[a][b];q.push({w+t[a][b],a,b,i});}}}}};dijkstra();cout<<dist[n][m][1]<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}
5. 船长
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//using i128 = __int128_t;
const ll inf = 1e18;
const int mod = 998244353;int qmi(int a,int b,int p){int res=1;while(b){if(b&1)res=res*a%p;b>>=1;a=a*a%p; }return res;
}void solve(){int n,k,pos;cin>>n>>k;k++;vector<pii> a(k);for(int i=0;i<k;i++){cin>>a[i].first;a[i].second=1;}pos=a[0].first;sort(a.begin(),a.end());int cnt=0;int inv2=qmi(2,mod-2,mod);while(a.size()>1){cnt++;vector<pii> ta;for(int i=0;i<a.size();i++){auto [id,p]=a[i];if(id&1){if(i<a.size()-1 && a[i+1].first==id+1){//和下一个可以合并continue;}else{//和下一个不能合并if(id==n){//处理轮空ta.push_back({(id+1)/2,p});if(id==pos) pos=(id+1)/2;continue;}if(id!=pos) p=p*inv2%mod;else pos=(pos+1)/2;ta.push_back({(id+1)/2,p});}}else{if(i!=0 && a[i-1].first==id-1){//偶数位置，且可以和上一个合并//1. 上一个是个士兵if(a[i-1].first!=pos){if(id!=pos){//这个也是士兵p=(p+a[i-1].second)*inv2%mod;ta.push_back({id/2,p});}else{//这个是qqp=p*(1-a[i-1].second+mod)%mod;ta.push_back({id/2,p});pos=id/2;}}else{//2. 上一个是qqp=a[i-1].second*(1-p+mod)%mod;ta.push_back({id/2,p});pos=id/2;}}else{//偶数位置，不可和上一个合并if(id!=pos) p=p*inv2%mod;else pos=(pos+1)/2;ta.push_back({id/2,p});}}}n=(n+1)/2;a=ta;}// cout<<"round: "<<cnt<<endl;cout<<a[0].second<<endl;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}