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;
}
Comments | NOTHING