https://ac.nowcoder.com/acm/contest/1107#question

没学会点分治。。。傻了。。。最后那个DFS的做法也不是很会 好像就是搜到一个点就和之前的所有的点比 同时更新后面的点。。。好难啊 今天更新下day2的题解 day2 读题场。。。

A-Easy h-index
题意:h-index 为至少有h篇论文被引用次数不小于h
很绕的一句话。。。
之后给一个数组 a0表示有a0篇论文被引了0次
做法:倒着扫一遍就成了。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 10;
 
int s[maxn];
int main()
{
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i <= n; ++i) {
            scanf("%d", &s[i]);
        }
        long long sum = 0;
        for (int i = n; i >= 0; --i) {
            sum += s[i];
            if (sum >= i) {//当论文总数超过了当前的i时 就可以跳出了
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}

B-Highter h-index

题意:花x个小时写的论文 能被引用x*a次 同时可以引用自己写的论文
思路:求最大h 不知道为啥 花一个小时写n篇论文 收获最大 n篇论文的引用数为 a,a+1,a+2,a+3....a+n-1引用数大于它的有n-i篇 a+i=n-i h=(n+a)/2

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7;
 
int main()
{
    int n, a;
    while (cin>>n) {
        cin >> a;
        cout << (n + a) / 2 << endl;
    }
    return 0;
}

F-sorting

题意:给你n个三元组 让你排序
排序规则

思路如上 不过可以倒数 似乎更简单 叉姐写的就是倒数的做法

//贴个倒数的 叉姐写的
#include <algorithm>
#include <cstdio>

const int N = 100000;

int a[N], b[N], c[N], ord[N];

bool cmp(int i, int j)
{
    auto x = c[i] * (1ULL * a[j] + b[j] + c[j]);
    auto y = c[j] * (1ULL * a[i] + b[i] + c[i]);
    if (x == y) {
        return i < j;
    }
    return x > y;
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++ i) {
            scanf("%d%d%d", a + i, b + i, c + i);
            ord[i] = i;
        }
        sort(ord, ord + n, cmp);
        for (int i = 0; i < n; ++ i) {
            printf("%d%c", ord[i] + 1, " \n"[i == n - 1]);
        }
    }
}

G-String Transformation

这个题我们队比较自豪
题意:有一个字符串 只包含a b c 之后可以在任意位置添加或者删除 aa bb abab
然后问给两个字符串 问经过变换是否可以变成一样的
之后我们可以发现规律哇 ab->aababb->ba
同理ba可以换为ab
a->aabab->bab
b->aba
按照这个规则化简 赛后发现 还有更厉害的做法 似乎两个c之间 a b的奇偶性质是相同的 明天敲一敲 这个肯定能完成
继续昨天的写 你看哈 我们简单的口胡一下 ab=ba a=bab b=aba无论怎么等价变化 ab的奇偶性都是一样的 我写写代码试试

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int maxn = 250000;
int c1[maxn];
int c2[maxn];
string s1, s2;

bool judge(int a, int b, int c, int d) {
	int c1 = 0;
	int c2 = 0;
	int c3 = 0;
	int c4 = 0;
	for (int i = a; i <= b; i++) {
		if (s1[i] == 'a') c1++;
		else if (s1[i] == 'b') c2++;
	}
	for (int i = c; i <= d; i++) {
		if (s2[i] == 'a')c3++;
		else if (s2[i] == 'b') c4++;
	}
	if (c1 % 2 != c3 % 2 || c2 % 2 != c4 % 2) {
		return 1;
	}
	else {
		return 0;
	}
}


int main() {
	int cnt1, cnt2;
	while (cin >> s1 >> s2) {
		s1 = s1 + 'c';
		s2 = s2 + 'c';
		c1[0] = c2[0] = 0;
		cnt1 = 0;
		cnt2 = 0;
		for (int i = 0; i < s1.length(); i++) {
			if (s1[i] == 'c') c1[++cnt1] = i;
		}
		for (int i = 0; i < s2.length(); i++) {
			if (s2[i] == 'c') c2[++cnt2] = i;
		}
		if (cnt1 != cnt2) {
			cout << "No" << endl;
			continue;
		}
		bool flag = 0;
		for (int i = 1; i <= cnt1 + 1; i++) {
			if (judge(c1[i - 1], c1[i], c2[i - 1], c2[i])) {
				flag = 1;
				break;
			}
		}
		if (flag) cout << "No" << endl;
		else cout << "Yes" << endl;
	}
	return 0;
}

K-2018
呜呜呜写的没自动保存。。。哭辽 给abcd
计算[a,b][c,d]中有多少对的乘积是2018的倍数
直接算就行 注意去重 因为只有 1 2 1009 2018是因子

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
static const int MOD = 2019;
typedef long long ll;

int main() {
	int a, b, c, d;
	while (cin >> a >> b >> c >> d) {
		int t1 = b / 1009 - (a - 1) / 1009;
		int t2 = b / 2018 - (a - 1) / 2018;
		int t3 = b / 2 - (a - 1) / 2;
		int a1 = d / 1009 - (c - 1) / 1009;
		int a2 = d / 2018 - (c - 1) / 2018;
		int a3 = d / 2 - (c - 1) / 2;
		ll s1 = 1ll * (t1 - t2) * a3;
		ll s2 = 1ll * t2 * (d - c + 1);
		ll s3 = 1ll * (a1 - a2) * (t3 - t2);
		ll s4 = 1ll * a2 * (b - a + 1 - t1);
		cout << s1 + s2 + s3 + s4 << endl;
	}
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。