牛客小白月赛44(还有没补的)

一步步慢慢走,终归是能走到山顶的

A.深渊水妖

就按照题目要求的去找就行了
代码

#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.顽皮恶魔

就是简单的bfs一遍,判断每一个植物的九宫格内是否存在保护伞就行了。
代码

#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.绝命沙虫

就按照题目要求的来就行了, 这里注意的就是精度的问题,例如 -1 可以写成 -0.99999999.反正就挺离谱的。以后注意了 【多学学这方面的技巧】!!!
代码

#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.丛林木马

这题很简单我们会发现答案就是 asize(b) + bsize(a), 但是由于他的数字太大这样写根本不可能。
但是我们可以转化为 a = an * 10^n-1 + an-1*10^n-2 + ... + a1 ---> 这里就想到不就是 t = t * 10 + ai(t 初始化为0, i∈(1, n))
所以说可以直接按照上面的公式写成 t = (t * 10 + ai) % mod; 不就可以了, 就不用高精度了。(不想写高精度!!!)
代码

#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.变异蛮牛

这里我的思路太局限了,没写出来,还是思考的太浅了。首先很明显这里的长度只会出现-1, 0, 1
1 -> 就是最大的那一个, 由于根是黑的,所以保证了1一定存在了。
但是当时没往下想,直接dfs, 但是交了WA了,才想到他不一定是从根节点开始的链啊!
这里其实换个方向想,长度为1,他这条链有啥特征呢!我们发现肯定是黑头黑尾的,那么这时候
换个思路想,那不就是C(2, cnt) 嘛cnt是黑点的数量。哇哇塞恍然大悟,但是要注意的是这里的cnt >= 2的,别漏掉单独一个点的黑点
所以答案就是 cnt * (cnt-1) / 2 + cnt;
代码

#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.幽暗统领

https://ac.nowcoder.com/acm/discuss/blogs?tagId=145684
过段时间在补,放个题解地址,好找

上一篇:《整数拼接》


下一篇:Android EditText输入框实现下拉且保存最近5个历史记录思路详解