codeforces round #427 div2
分类:
IT文章
•
2024-03-27 20:42:37
A:读懂题，乘一下判断大小就行了
![]()
#include<bits/stdc++.h>
using namespace std;
int main()
{
int s, v1, v2, t1, t2;
scanf("%d%d%d%d%d", &s, &v1, &v2, &t1, &t2);
int ans1 = v1 * s + t1 * 2, ans2 = v2 * s + t2 * 2;
if(ans1 == ans2) puts("Friendship");
else if(ans1 < ans2) puts("First");
else puts("Second");
return 0;
}
View Code
B:又是桶。。。cf怎么这么喜欢桶，当然把最小的位换成9是最好的，那么10个数字开10个桶，暴力删除每位改成9就行了，只是while要放在前面枚举pos
![]()
#include<bits/stdc++.h>
using namespace std;
int tot[10], sum, ans;
char s[1000010];
int main()
{
int k;
scanf("%d%s", &k, s);
int len = strlen(s);
for(int i = 0; i < len; ++i) ++tot[s[i] - '0'], sum += s[i] - '0';
int pos = 0;
while(sum < k)
{
while(tot[pos] == 0) ++pos;
sum += 9 - pos;
--tot[pos];
++ans;
}
printf("%d
", ans);
return 0;
}
View Code
C:很明显不能暴力每次把所有星星+1，这是做不到的，但是看见c很小，那么我们预处理出c+1种情况就行了，可以用二维前缀和或二维bit，注意星星的位置可以重叠，考试的时候脑子坏了重新写了一遍，skip罚时爆炸，30min没了。。。
二维前缀和
![]()
#include<bits/stdc++.h>
using namespace std;
int a[11][110][110], mark[110][110];
vector<int> b[11][110][110];
int main()
{
int n, q, c;
scanf("%d%d%d", &n, &q, &c);
for(int i = 1; i <= n; ++i)
{
int x, y, s;
scanf("%d%d%d", &x, &y, &s);
mark[x][y] = 1;
b[0][x][y].push_back(s);
}
for(int k = 0; k <= 10; ++k)
for(int i = 1; i <= 101; ++i)
for(int j = 1; j <= 101; ++j)
{
int delta = 0;
if(k > 0)
{
for(int l = 0; l < b[k - 1][i][j].size(); ++l)
{
b[k][i][j].push_back((b[k - 1][i][j][l] + 1) % (c + 1));
delta += b[k][i][j][l];
}
}
else
{
for(int l = 0; l < b[k][i][j].size(); ++l)
delta += b[k][i][j][l];
}
a[k][i][j] = a[k][i][j - 1] + a[k][i - 1][j] - a[k][i - 1][j - 1] + delta;
}
for(int i = 1; i <= q; ++i)
{
int t, x1, y1, x2, y2;
scanf("%d%d%d%d%d", &t, &x1, &y1, &x2, &y2);
int sum = a[t % (c + 1)][x2][y2] - a[t % (c + 1)][x2][y1 - 1] - a[t % (c + 1)][x1 - 1][y2] + a[t % (c + 1)][x1 - 1][y1 - 1];
printf("%d
", sum);
}
return 0;
}
View Code
![]()
#include<bits/stdc++.h>
using namespace std;
int a[11][110][110], mark[110][110];
int tree[11][110][110], x[1000010], y[1000010], s[100010][11];
int lowbit(int i)
{
return i & (-i);
}
void update(int k, int x, int y, int delta)
{
for(int i = x; i <= 101; i += lowbit(i))
for(int j = y; j <= 101; j += lowbit(j))
tree[k][i][j] += delta;
}
int query(int k, int x, int y)
{
int ret = 0;
for(int i = x; i; i -= lowbit(i))
for(int j = y; j; j -= lowbit(j)) ret += tree[k][i][j];
return ret;
}
int main()
{
int n, q, c;
scanf("%d%d%d", &n, &q, &c);
for(int i = 1; i <= n; ++i)
scanf("%d%d%d", &x[i], &y[i], &s[i][0]);
for(int k = 0; k <= 10; ++k)
for(int l = 1; l <= n; ++l)
{
if(k == 0) update(k, x[l], y[l], s[l][0]);
else
{
s[l][k] = (s[l][k - 1] + 1) % (c + 1);
update(k, x[l], y[l], s[l][k]);
}
}
for(int i = 1; i <= q; ++i)
{
int t, x1, y1, x2, y2;
scanf("%d%d%d%d%d", &t, &x1, &y1, &x2, &y2);
int sum = query(t % (c + 1), x2, y2) - query(t % (c + 1), x2, y1 - 1) - query(t % (c + 1), x1 - 1, y2) + query(t % (c + 1), x1 - 1, y1 - 1);
printf("%d
", sum);
}
return 0;
}
