A、
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int T; cin >> T;
while(T--){
vector <int> G;
for(int i = 1; i <= 3; i++){
int x; cin >> x;
G.push_back(x);
}
sort(G.begin(), G.end());
cout << G[1] << endl;
}
return 0;
}
B、
可以发现，找到最大的字母即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int T; cin >> T;
while(T--){
int n; cin >> n;
string s;
cin >> s;
int len = s.length();
int maxn = 0;
for(int i = 0; i < len; i++)
maxn = max(maxn, (int)s[i] - 'a');
cout << maxn + 1 << endl;
}
return 0;
}
C、
排序后按照题目要求来即可。也可以用堆来做。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 1000100
struct node{
int w;
int id;
bool operator < (const node& a) const{
return w < a.w;
}
} ;
vector <node> G;
int ans[N];
int main(){
int T; cin >> T;
while(T--){
G.clear();
int n; cin >> n;
for(int i = 1; i <= n; i++){
int x; cin >> x;
G.push_back((node){x, i});
}
sort(G.begin(), G.end());
for(int i = 0; i < G.size() - 1; i++){
ans[G[i].id] = -(G[G.size() - 1].w - G[i].w);
}
ans[G[G.size()-1].id] = G[G.size()-1].w - G[G.size() - 2].w;
for(int i = 1; i <= n; i++)
cout << ans[i] << " ";
cout << endl;
}
}
D、
按照题目要求，可以线性找到一段平的区域，然后判断其是否符合三个要求。没找到一个统计一下，最后判断是否存在且唯一即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
int n;
int a[N];
int main(){
int T; cin >> T;
while(T--){
for(int i = 1; i <= n; i++)
a[i] = 0;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
int l = 1, r = 1;
int sum = 0;
for(int i = 1; i <= n; i = r){
while(a[l] == a[r+1]) r++;
if((l == 1 || a[l-1] > a[l]) && (r == n || a[r] < a[r+1]))
sum++;
l = r = r + 1;
}
if(sum == 1) puts("YES");
else puts("NO");
}
return 0;
}
E、
分三种情况：不做变换，变换第一个 \(0\), 变换最后一个 \(1\)。贪心正确性显然。三个情况取 \(max\) 即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define int long long
vector <int> G;
int n;
signed main(){
int T; cin >> T;
while(T--){
G.clear();
G.push_back(-1);
cin >> n;
for(int i = 1; i <= n; i++){
int x; cin >> x;
G.push_back(x);
}
int sum = 0;
int ans3 = 0;
for(int i = n; i; i--){
if(G[i] == 0) sum++;
else ans3 += sum;
}
int id = 0;
for(int i = 1; i <= n; i++)
if(G[i] == 0){
G[i] ^= 1;
id = i;
break;
}
int ans1 = 0;
sum = 0;
for(int i = n; i; i--){
if(G[i] == 0) sum++;
else ans1 += sum;
}
sum = 0;
int ans2 = 0;
G[id] ^= 1;
for(int i = n; i; i--){
if(G[i] == 1){
G[i] ^= 1;
break;
}
}
for(int i = n; i; i--){
if(G[i] == 0) sum++;
else ans2 += sum;
}
cout << max(ans1, max(ans2, ans3)) << endl;
}
return 0;
}
F、
首先存在贪心：优先做当前能做的所有题中分值最大的那个肯定更优。
然后二分天数即可。
考虑二分的 \(check\)：可以发现，当休息天数为 \(k\) 时，我们永远只会做前 \(k + 1\) 大（如果题目足够多的话）。之后按照循环填入每一段（每一段内部的顺序肯定也是相等的）。最后统计总和是否超过 \(c\) 即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 200100
#define int long long
int a[N];
int n, c, days;
bool check(int lim){
int sum = 0;
for(int j = 1; j <= lim + 1; j++){
for(int i = j; i <= days; i += lim + 1){
// printf("i: %d sum: %d\n", i, sum);
sum += a[max(n - j + 1, 0ll)];
}
}
return sum >= c;
}
signed main(){
int T; cin >> T;
while(T--){
cin >> n >> c >> days;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 0, r = days + 100;
int ans = -1;
while(l <= r){
int mid = l + r >> 1;
if(check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
if(ans == -1) cout << "Impossible" << endl;
else if(ans >= days) cout << "Infinity" << endl;
else cout << ans << endl;
}
return 0;
}
G、
首先，如果不能跳跃，那么肯定就是 \(S\) 到 \(T\) 的链的异或值。
考虑跳跃。那么我们的路径就成为了以 \(S\) 且不越过 \(T\) 的一条链加上以 \(T\) 为起点的另外一条链。
为什么是链？因为走回头路相当于这一段是无效操作。
为什么 \(S\) 开始不能越过 \(T\)? 因为直接走路的话不能进 \(T\)。
为什么 \(T\) 可以越过 \(S\)? 因为可以先去 \(S\) 的另外一棵子树，再去这一课子树。
上述操作也包含了不传送的情况。（原地TP）。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
struct node{
int u, v, next;
ll w;
} t[N << 1];
int head[N];
int bian = 0;
inline void addedge(int u, int v, ll w){
t[++bian] = (node){u, v, head[u], w}, head[u] = bian;
return ;
}
int n, S, T;
map <ll, bool> g;
ll dis1[N];
ll dis2[N];
bool vis1[N], vis2[N];
void dfs1(int u){
if(u == T) return ;
vis1[u] = 1;
for(int i = head[u]; i; i = t[i].next){
int v = t[i].v;
if(!vis1[v]){
dis1[v] = dis1[u] ^ t[i].w;
dfs1(v);
}
}
return ;
}
void dfs2(int u){
// if(u == S) return ;
vis2[u] = 1;
for(int i = head[u]; i; i = t[i].next){
int v = t[i].v;
if(!vis2[v]){
dis2[v] = dis2[u] ^ t[i].w;
dfs2(v);
}
}
return ;
}
void clear(int n){
g.clear();
for(int i = 1; i <= n; i++)
dis1[i] = dis2[i] = 0;
for(int i = 1; i <= n; i++)
head[i] = 0, vis1[i] = vis2[i] = 0;
bian = 0;
return ;
}
int main(){
int testcase; cin >> testcase;
while(testcase--){
clear(n);
cin >> n >> S >> T;
for(int i = 1; i < n; i++){
int u, v, w;
cin >> u >> v >> w;
addedge(u, v, w);
addedge(v, u, w);
}
dfs1(S);
dfs2(T);
for(int i = 1; i <= n; i++)
if(vis1[i]) g[dis1[i]] = 1;
bool flag = 0;
for(int i = 1; i <= n; i++){
if(vis2[i] && i != T)
if(g[dis2[i]] == 1){
flag = 1;
break;
}
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}