T1 - 小田的四则运算
因为三个数是升序排序的，只会有三种情况：
a+b+c、(a+b)*c、a*b*c
直接取三个中的最大值即可。
#include <bits/stdc++.h>
using namespace std;
int a[3];
int main() {
cin >> a[0] >> a[1] >> a[2];
int x = a[0]+a[1]+a[2];
int y = (a[0]+a[1])*a[2];
int z = a[0]*a[1]*a[2];
cout << max(x, max(y, z));
return 0;
}
T2 - 小田的 gcd 构造
只要输出一种满足条件的答案即可。
最大值能取到 5e18，而 x,y,z 都是小于等于 1e18的，所以可以取一个 5e18/z*z，这样一定是 z 的倍数，然后另外一个数字取 z，这样的话一定满足题目的三个条件。
#include <bits/stdc++.h>
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
long long x, y, z, maxx=5e18;
int main() {
freopen("gcd.in", "r", stdin);
freopen("gcd.out", "w", stdout);
qwq;
cin >> x >> y >> z;
cout << z << " " << maxx/z*z;
return 0;
}
T3 - 小田的山峰数组
双指针枚举的思想，枚举 a[1]~a[i] 为第一个区间，那么再来个变量 j，来找到这个情况下第一个满足山峰数组的 j，那么这次的情况总数就是 n-j个，求总和即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
long long n, a[N], s[N], res;
int main() {
freopen("mountain.in", "r", stdin);
freopen("mountain.out", "w", stdout);
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
s[i] = s[i-1]+a[i];
}
int j=2;
for (int i=1; i<n-1; i++) {
if (s[i] >= s[n]-s[i]) break;
while (s[j]-s[i]<=s[i] or s[j]-s[i]<=s[n]-s[j]) j++;
res += n-j;
}
cout << res;
return 0;
}
T4 - Dota2参议院
题目描述
Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）
Dota2 阿哈利姆参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们将进行轮流投票。在每一轮中，每一位参议员都可以行使两项权利中的一项：
- 禁止一名参议员的投票权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
- 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定下一次的游戏更新。
给你一个字符串 s 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的阵营做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定更新。输出应该是 "Radiant" 或 "Dire" 。
输入描述
一行，表示给定的字符串，字符串只包含R和D
输出描述
输出"Radint" 或者 "Dire"
输入输出样例
输入 #1
RD
输出 #1
Radint
输入 #2
RDD
输出 #2
Dire
说明/提示
【数据范围】 字符串只包含 R 或 D 【样例1解释】
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人
【样例2解释】
第 1 轮时，第一个`来自 Radiant 阵营的`参议员可以使用第一项权利禁止第二个参议员的权利。
`这一轮中，`第二个`来自 Dire 阵营的`参议员会将被跳过，因为他的权利被禁止了。
`这一轮中，`第三个`来自 Dire 阵营的`参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
【解析】 贪心+队列模拟 以天辉参议员为例，当一名天辉方参议员行使权力时：
- 所有参议员都是天辉方，宣布胜利
- 挑选一名对方阵营的参议员，行使禁止权力，那应该挑选谁呢？应该贪心的挑选按照投票顺序的下一名夜宴参议员，证明：只能挑选一名，应该尽可能挑选可以最早行使投票权利的那一名议员，如果挑选了其他较晚投票的议员，那么等到最早可以进行投票的那一名议员行使权利时，一名天辉方议员就会丧失权利，这样就得不偿失了。
使用队列模拟实现
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int q1[2*N], q2[2*N], hh1=0, tt1=-1, hh2=0, tt2=-1;
int main()
{
string s;
cin >> s;
int n = s.size();
for (int i = 0; i < n; i++)
{
if (s[i] == 'R') q1[++tt1] = i;
else q2[++tt2] = i;
}
while (hh1<=tt1 && hh2 <= tt2)
{
if (q1[hh1] < q2[hh2])
q1[++tt1] = q1[hh1]+n;
else
q2[++tt2] = q2[hh2]+n;
hh1++, hh2++;
}
if (hh1 > tt1) cout << "Dire";
else cout << "Radiant";
}
T5 小W走迷宫
思路 :广搜模版题
#include<bits/stdc++.h>
using namespace std;
int n,m,sb1,sb2;
char maps[100][100];
struct node{
int x,y,step;
};
int book[100][100];
int nxt[4][2]={1,0,0,1,-1,0,0,-1};
int bfs(){
queue <node> que;
node a={sb1,sb2,0};
que.push(a);
while(!que.empty()){
node now=que.front();
que.pop();
for(int i=0;i<4;i++){
node next=now;
next.x+=nxt[i][0];
next.y+=nxt[i][1];
next.step++;
if(next.x>n||next.x<1||next.y>m||next.y<1||book[next.x][next.y]==1||maps[next.x][next.y]=='#'){
continue;
}if(maps[next.x][next.y]=='*') return next.step;
book[next.x][next.y]=1;
que.push(next);
}
}
return -1;
}int main(){
freopen("mg.in","r",stdin);
freopen("mg.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>maps[i][j];
if(maps[i][j]=='@'){
sb1=i;
sb2=j;
}
}
}cout<<bfs();
}
T6 小W去旅游
多源最短路 , 模板题
//多源最短路，用floyd算法
#include <bits/stdc++.h>
using namespace std;
int dist[50][50],n,m,x,y;//可能有重边
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
int main(){
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j) dist[i][j]=0;//去自环
else dist[i][j]=1e9;
}
while(m--){
int a,b,l;
cin>>a>>b>>l;
dist[a][b]=min(dist[a][b],l);
dist[b][a]=dist[a][b];//无向图
}
floyd();
cin>>x>>y;
if(dist[x][y]==1e9) cout<<"No path";
else cout<<dist[x][y];
return 0;
}
