Walking slowly step by step, you can finally reach the top of the mountain
A. Abyss water demon
Just look for it according to the requirements of the topic
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template <class T>
inline bool in(T &ret)
{
char c;T sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void out(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
out(x/10);
putchar(x%10+'0');
}
const int N = 1e5 + 100;
int a[N];
struct node {
int l, r;
}res[N];
int main()
{
int T;cin >> T;
while(T-- ) {
int n;cin >> n;
for(int i = 0;i < n;i ++ ) cin >> a[i];
int l = 0, last = 0, cnt = 0, maxn = 0;
while(l < n) {
while(a[l+1] >= a[l] && l < n) l ++;
res[cnt++] = {last+1, l+1};
maxn = max(a[l] - a[last], maxn);
last = ++l;
}
// cout << cnt << endl;
for(int i = 0;i < cnt;i ++ ) {
if(a[res[i].r-1] - a[res[i].l-1] == maxn)
cout << res[i].l << " " << res[i].r << " ";
}
}
return 0;
}
B. Naughty devil
It is simply bfs once to judge whether there is an umbrella in each plant's Jiugong grid.
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template <class T>
inline bool in(T &ret)
{
char c;T sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void out(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
out(x/10);
putchar(x%10+'0');
}
const int N = 1e3 + 100;
char g[N][N];
int main()
{
IOS;
int T;cin >> T;
while(T--) {
int n, m;cin >> n >> m;
int res = 0;
for(int i = 1;i <= n;i ++ ) {
for(int j = 1;j <= m;j ++ ) cin >> g[i][j];
}
for(int i = 1;i <= n;i ++ ) {
for(int j = 1;j <= m;j ++ ) {
if(g[i][j] == 'P') {
int f = 1;
for(int p = -1; p <= 1;p ++ ) {
for(int q = -1; q <= 1; q ++ ) {
if(g[p+i][q+j] == '*' && p + i <= n && q+j <= m) {
f = 0;break;
}
}
}
res += f;
}
}
}
cout << res << endl;
}
return 0;
}
C. Deadly Sandworm
Just follow the requirements of the topic. What we pay attention to here is the problem of accuracy. For example, - 1 can be written as -0.9999999 It's crazy anyway. Later, I paid attention to [learn more skills in this regard]!!!
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template <class T>
inline bool in(T &ret)
{
char c;T sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void out(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
out(x/10);
putchar(x%10+'0');
}
int main()
{
int T;cin >> T;
while(T--) {
int n;cin >> n;
double M;cin >> M;
int m = (M-0.999999999999)*100;
int a = 0, b = 0, res = 0;
while(n) {
a = n * 100, b = min(10000, n * m);
n = a / 200;
res += b / 10 + a / 10;
}
cout << res << endl;
}
return 0;
}
D. Jungle Trojan horse
This question is very simple. We will find that the answer is asize(b) + bsize(a), but because his number is too large, it is impossible to write this.
But we can convert it into a = an * 10 ^ n-1 + an-1 * 10 ^ n-2 ++ A1 -- > here i think t = t * 10 + ai(t is initialized to 0, i ∈ (1, n))
Therefore, it can be directly written as t = (t * 10 + AI)% mod according to the above formula; No, it's OK. There's no need for high precision. (don't want to write high precision!!!)
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template <class T>
inline bool in(T &ret)
{
char c;T sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void out(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
out(x/10);
putchar(x%10+'0');
}
const int N = 1e5 + 100;
ll a[N];
const ll mod = 998244353;
int main()
{
int T;cin >> T;
while(T--) {
string a, b;cin >> a >> b;
ll t1 = 0, t2 = 0, aa = (int)a.size(), bb = (int)b.size();
for(char ch : a) {
int c = ch - '0';
t1 = (t1 * 10 + c) % mod;
}
t1 = t1 * bb % mod;
for(char ch: b) {
int c = ch - '0';
t2 = (t2 * 10 + c) % mod;
}
t2 = t2 * aa % mod;
// cout << t1 << " " << t2 << endl;
ll res = (t1 + t2) % mod;
cout << res << endl;
}
return 0;
}
E. Mutant bull
My thinking here is too limited. I didn't write it out, but my thinking is too shallow. First of all, it is obvious that the length here will only appear - 1, 0, 1
1 - > is the largest one. Because the root is black, it ensures that 1 must exist.
But I didn't think about it at that time. I directly dfs, but after I handed in the WA, I thought he didn't necessarily start from the root node!
In fact, in another direction, if the length is 1, what are the characteristics of his chain! We found it must be black headed and black tailed, so at this time
To put it another way, that's C(2, cnt). CNT is the number of black spots. Wow, wow, you suddenly realize, but you should pay attention to the cnt > = 2 here. Don't miss the black spot of a single point
So the answer is cnt * (cnt-1) / 2 + cnt;
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template <class T>
inline bool in(T &ret)
{
char c;T sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void out(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
out(x/10);
putchar(x%10+'0');
}
const int N = 2e5 + 100;
int h[N], e[N*2], ne[N*2] , idx;
void add(int x, int y) {
e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}
ll res = 0;
void dfs(int fa, int u, int t) {
res += t;
for(int i = h[u]; ~i ;i = ne[i]) {
int j = e[i];
if(j != fa) {
dfs(u, j, !t);
}
}
return ;
}
int main()
{
IOS;
int T;cin >> T;
while(T--) {
int n;cin >> n;
for(int i = 1;i <= n;i ++ ) h[i] = -1;
idx = 0;
res = 0;
for(int i = 0;i < n-1;i ++ ) {
int u, v;
cin >> u >> v;
// cout << u << ' ' << v << endl;
add(u, v);add(v, u);
}
dfs(-1, 1, 1);
res = res * (res - 1) / 2 + res;
cout << res << endl;
}
return 0;
}
F. Dark Commander
https://ac.nowcoder.com/acm/discuss/blogs?tagId=145684
I'll fill it up after a while. Put an address to solve the problem. It's easy to find