slove 4/11
rank 163
补题 4/10
---------------------------------------------------
6659 Acesrc and Good Numbers
首先确定答案不会太大，写个状压跑一跑，能跑出所有答案（或者直接oeis）
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll a1[84] = { 0,1,199981,199982,199983,199984,199985,199986,199987,199988,199989,199990,200000,200001,1599981,1599982,1599983,1599984,1599985,1599986,1599987,1599988,1599989,1599990,2600000,2600001,13199998,35000000,35000001,35199981,35199982,35199983,35199984,35199985,35199986,35199987,35199988,35199989,35199990,35200000,35200001,117463825,500000000,500000001,500199981,500199982,500199983,500199984,500199985,500199986,500199987,500199988,500199989,500199990,500200000,500200001,501599981,501599982,501599983,501599984,501599985,501599986,501599987,501599988,501599989,501599990,502600000,502600001,513199998,535000000,535000001,535199981,535199982,535199983,535199984,535199985,535199986,535199987,535199988,535199989,535199990,535200000,535200001,1111111110 };
ll a2[14] = { 0,28263827,35000000,242463827,500000000,528263827,535000000,10000000000,10028263827,10035000000,10242463827,10500000000,10528263827,10535000000 };
ll a3[36] = { 0,371599983,371599984,371599985,371599986,371599987,371599988,371599989,371599990,371599991,371599992,500000000,10000000000,10371599983,10371599984,10371599985,10371599986,10371599987,10371599988,10371599989,10371599990,10371599991,10371599992,10500000000,20000000000,20371599983,20371599984,20371599985,20371599986,20371599987,20371599988,20371599989,20371599990,20371599991,20371599992,20500000000 };
ll a4[48] = { 0,499999984,499999985,499999986,499999987,499999988,499999989,499999990,499999991,499999992,499999993,500000000,10000000000,10499999984,10499999985,10499999986,10499999987,10499999988,10499999989,10499999990,10499999991,10499999992,10499999993,10500000000,20000000000,20499999984,20499999985,20499999986,20499999987,20499999988,20499999989,20499999990,20499999991,20499999992,20499999993,20500000000,30000000000,30499999984,30499999985,30499999986,30499999987,30499999988,30499999989,30499999990,30499999991,30499999992,30499999993,30500000000};
ll a5[5] = { 0,10000000000,20000000000,30000000000,40000000000 };
ll a6[72] = { 0,9500000000,9628399986,9628399987,9628399988,9628399989,9628399990,9628399991,9628399992,9628399993,9628399994,9628399995,10000000000,19500000000,19628399986,19628399987,19628399988,19628399989,19628399990,19628399991,19628399992,19628399993,19628399994,19628399995,20000000000,29500000000,29628399986,29628399987,29628399988,29628399989,29628399990,29628399991,29628399992,29628399993,29628399994,29628399995,30000000000,39500000000,39628399986,39628399987,39628399988,39628399989,39628399990,39628399991,39628399992,39628399993,39628399994,39628399995,40000000000,49500000000,49628399986,49628399987,49628399988,49628399989,49628399990,49628399991,49628399992,49628399993,49628399994,49628399995,50000000000,59500000000,59628399986,59628399987,59628399988,59628399989,59628399990,59628399991,59628399992,59628399993,59628399994,59628399995 };
ll a7[49] = { 0,9465000000,9471736170,9500000000,9757536170,9965000000,9971736170,10000000000,19465000000,19471736170,19500000000,19757536170,19965000000,19971736170,20000000000,29465000000,29471736170,29500000000,29757536170,29965000000,29971736170,30000000000,39465000000,39471736170,39500000000,39757536170,39965000000,39971736170,40000000000,49465000000,49471736170,49500000000,49757536170,49965000000,49971736170,50000000000,59465000000,59471736170,59500000000,59757536170,59965000000,59971736170,60000000000,69465000000,69471736170,69500000000,69757536170,69965000000,69971736170};
ll a8[344] = { 0,9465000000,9486799989,9486799990,9486799991,9486799992,9486799993,9486799994,9486799995,9486799996,9486799997,9497400000,9498399989,9498399990,9498399991,9498399992,9498399993,9498399994,9498399995,9498399996,9498399997,9500000000,9882536171,9965000000,9986799989,9986799990,9986799991,9986799992,9986799993,9986799994,9986799995,9986799996,9986799997,9997400000,9998399989,9998399990,9998399991,9998399992,9998399993,9998399994,9998399995,9998399996,9998399997,10000000000,19465000000,19486799989,19486799990,19486799991,19486799992,19486799993,19486799994,19486799995,19486799996,19486799997,19497400000,19498399989,19498399990,19498399991,19498399992,19498399993,19498399994,19498399995,19498399996,19498399997,19500000000,19882536171,19965000000,19986799989,19986799990,19986799991,19986799992,19986799993,19986799994,19986799995,19986799996,19986799997,19997400000,19998399989,19998399990,19998399991,19998399992,19998399993,19998399994,19998399995,19998399996,19998399997,20000000000,29465000000,29486799989,29486799990,29486799991,29486799992,29486799993,29486799994,29486799995,29486799996,29486799997,29497400000,29498399989,29498399990,29498399991,29498399992,29498399993,29498399994,29498399995,29498399996,29498399997,29500000000,29882536171,29965000000,29986799989,29986799990,29986799991,29986799992,29986799993,29986799994,29986799995,29986799996,29986799997,29997400000,29998399989,29998399990,29998399991,29998399992,29998399993,29998399994,29998399995,29998399996,29998399997,30000000000,39465000000,39486799989,39486799990,39486799991,39486799992,39486799993,39486799994,39486799995,39486799996,39486799997,39497400000,39498399989,39498399990,39498399991,39498399992,39498399993,39498399994,39498399995,39498399996,39498399997,39500000000,39882536171,39965000000,39986799989,39986799990,39986799991,39986799992,39986799993,39986799994,39986799995,39986799996,39986799997,39997400000,39998399989,39998399990,39998399991,39998399992,39998399993,39998399994,39998399995,39998399996,39998399997,40000000000,49465000000,49486799989,49486799990,49486799991,49486799992,49486799993,49486799994,49486799995,49486799996,49486799997,49497400000,49498399989,49498399990,49498399991,49498399992,49498399993,49498399994,49498399995,49498399996,49498399997,49500000000,49882536171,49965000000,49986799989,49986799990,49986799991,49986799992,49986799993,49986799994,49986799995,49986799996,49986799997,49997400000,49998399989,49998399990,49998399991,49998399992,49998399993,49998399994,49998399995,49998399996,49998399997,50000000000,59465000000,59486799989,59486799990,59486799991,59486799992,59486799993,59486799994,59486799995,59486799996,59486799997,59497400000,59498399989,59498399990,59498399991,59498399992,59498399993,59498399994,59498399995,59498399996,59498399997,59500000000,59882536171,59965000000,59986799989,59986799990,59986799991,59986799992,59986799993,59986799994,59986799995,59986799996,59986799997,59997400000,59998399989,59998399990,59998399991,59998399992,59998399993,59998399994,59998399995,59998399996,59998399997,60000000000,69465000000,69486799989,69486799990,69486799991,69486799992,69486799993,69486799994,69486799995,69486799996,69486799997,69497400000,69498399989,69498399990,69498399991,69498399992,69498399993,69498399994,69498399995,69498399996,69498399997,69500000000,69882536171,69965000000,69986799989,69986799990,69986799991,69986799992,69986799993,69986799994,69986799995,69986799996,69986799997,69997400000,69998399989,69998399990,69998399991,69998399992,69998399993,69998399994,69998399995,69998399996,69998399997,70000000000,79465000000,79486799989,79486799990,79486799991,79486799992,79486799993,79486799994,79486799995,79486799996,79486799997,79497400000,79498399989,79498399990,79498399991,79498399992,79498399993,79498399994,79498399995,79498399996,79498399997,79500000000,79882536171,79965000000,79986799989,79986799990,79986799991,79986799992,79986799993,79986799994,79986799995,79986799996,79986799997,79997400000,79998399989,79998399990,79998399991,79998399992,79998399993,79998399994,79998399995,79998399996,79998399997 };
ll a9[9] = { 0,10000000000,20000000000,30000000000,40000000000,50000000000,60000000000,70000000000,80000000000 };
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int d;
ll n;
sc("%d%lld", &d, &n);
if (d == 1)
{
for (int i = 83; i >= 0; i--)
{
if (a1[i] <= n)
{
printf("%lld\n", a1[i]);
goto qwe;
}
}
}
else if (d == 2)
{
for (int i = 13; i >= 0; i--)
{
if (a2[i] <= n)
{
printf("%lld\n", a2[i]);
goto qwe;
}
}
}
else if (d == 3)
{
for (int i = 35; i >= 0; i--)
{
if (a3[i] <= n)
{
printf("%lld\n", a3[i]);
goto qwe;
}
}
}
else if (d == 4)
{
for (int i = 47; i >= 0; i--)
{
if (a4[i] <= n)
{
printf("%lld\n", a4[i]);
goto qwe;
}
}
}
else if (d == 5)
{
for (int i = 4; i >= 0; i--)
{
if (a5[i] <= n)
{
printf("%lld\n", a5[i]);
goto qwe;
}
}
}
else if (d == 6)
{
for (int i = 71; i >= 0; i--)
{
if (a6[i] <= n)
{
printf("%lld\n", a6[i]);
goto qwe;
}
}
}
else if (d == 7)
{
for (int i = 48; i >= 0; i--)
{
if (a7[i] <= n)
{
printf("%lld\n", a7[i]);
goto qwe;
}
}
}
else if (d == 8)
{
for (int i = 343; i >= 0; i--)
{
if (a8[i] <= n)
{
printf("%lld\n", a8[i]);
goto qwe;
}
}
}
else if (d == 9)
{
for (int i = 8; i >= 0; i--)
{
if (a9[i] <= n)
{
printf("%lld\n", a9[i]);
goto qwe;
}
}
}
qwe:;
}
} 6665 Calabash and Landlord
有两个正方形，问你将这个平面分为了几块不连通的区域。
先离散化，然后暴力每条边会产生的不连通区域，然后跑dfs连通块。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
struct point
{
ll x;
ll y;
void print()
{
pr("%lld %lld\n", x, y);
}
}a[4], b[4];
ll x[10];
ll y[10];
int s[30][30];
bool vis[30];
void calc(point q, point w)
{
if (q.x == w.x)
{
if (q.y > w.y)
swap(q, w);
//lie
int op = q.x;
if (q.y == 1)
{
if (w.y == 1)
{
return;
}
else if (w.y == 2)
{
s[5 + op][5 + op + 1] = 0;
s[5 + op + 1][5 + op] = 0;
}
else if (w.y == 3)
{
s[5 + op][5 + op + 1] = 0;
s[5 + op + 1][5 + op] = 0;
s[5 * 2 + op][5 * 2 + op + 1] = 0;
s[5 * 2 + op + 1][5 * 2 + op] = 0;
}
else if (w.y == 4)
{
s[5 + op][5 + op + 1] = 0;
s[5 + op + 1][5 + op] = 0;
s[5 * 2 + op][5 * 2 + op + 1] = 0;
s[5 * 2 + op + 1][5 * 2 + op] = 0;
s[5 * 3 + op][5 * 3 + op + 1] = 0;
s[5 * 3 + op + 1][5 * 3 + op] = 0;
}
}
else if (q.y == 2)
{
if (w.y == 2)
{
return;
}
else if (w.y == 3)
{
s[5 * 2 + op][5 * 2 + op + 1] = 0;
s[5 * 2 + op + 1][5 * 2 + op] = 0;
}
else if (w.y == 4)
{
s[5 * 2 + op][5 * 2 + op + 1] = 0;
s[5 * 2 + op + 1][5 * 2 + op] = 0;
s[5 * 3 + op][5 * 3 + op + 1] = 0;
s[5 * 3 + op + 1][5 * 3 + op] = 0;
}
}
else if (q.y == 3)
{
if (w.y == 3)
{
return;
}
else if (w.y == 4)
{
s[5 * 3 + op][5 * 3 + op + 1] = 0;
s[5 * 3 + op + 1][5 * 3 + op] = 0;
}
}
}
else
{
if (q.x > w.x)
swap(q, w);
//hang
int op = q.y;
if (q.x == 1)
{
if (w.x == 1)
{
return;
}
else if (w.x == 2)
{
s[5 * op + 2][5 * op + 2 - 5] = 0;
s[5 * op + 2 - 5][5 * op + 2] = 0;
}
else if (w.x == 3)
{
s[5 * op + 2][5 * op + 2 - 5] = 0;
s[5 * op + 2 - 5][5 * op + 2] = 0;
s[5 * op + 3][5 * op + 3 - 5] = 0;
s[5 * op + 3 - 5][5 * op + 3] = 0;
}
else if (w.x == 4)
{
s[5 * op + 2][5 * op + 2 - 5] = 0;
s[5 * op + 2 - 5][5 * op + 2] = 0;
s[5 * op + 3][5 * op + 3 - 5] = 0;
s[5 * op + 3 - 5][5 * op + 3] = 0;
s[5 * op + 4][5 * op + 4 - 5] = 0;
s[5 * op + 4 - 5][5 * op + 4] = 0;
}
}
else if (q.x == 2)
{
if (w.x == 2)
{
return;
}
else if (w.x == 3)
{
s[5 * op + 3][5 * op + 3 - 5] = 0;
s[5 * op + 3 - 5][5 * op + 3] = 0;
}
else if (w.x == 4)
{
s[5 * op + 3][5 * op + 3 - 5] = 0;
s[5 * op + 3 - 5][5 * op + 3] = 0;
s[5 * op + 4][5 * op + 4 - 5] = 0;
s[5 * op + 4 - 5][5 * op + 4] = 0;
}
}
else if (q.x == 3)
{
if (w.x == 3)
{
return;
}
else if (w.x == 4)
{
s[5 * op + 4][5 * op + 4 - 5] = 0;
s[5 * op + 4 - 5][5 * op + 4] = 0;
}
}
}
}
void dfs(int index) {
for (int i = 1; i <= 25; ++i) {
if (!vis[i] && s[i][index] == 1) {
vis[i] = true;
dfs(i);
}
}
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
for (int i = 1; i <= 25; i++)
for (int j = 1; j <= 25; j++)
s[i][j] = 0;
for (int i = 1; i <= 25; i++)
{
if (i - 5 >= 1)
s[i][i - 5] = 1;
if (i + 5 <= 25)
s[i][i + 5] = 1;
}
for (int i = 1; i <= 25; i++)
{
if (i % 5 != 0)
{
if (i + 1 <= 25)
s[i][i + 1] = 1;
}
if (i % 5 != 1)
{
if (i - 1 >= 1)
s[i][i - 1] = 1;
}
}
/*for (int i = 1; i <= 25; i++)
for (int j = 1; j <= 25; j++)
printf("%d%c", s[i][j], j == 25 ? '\n' : ' ');*/
sc("%lld%lld%lld%lld", &a[0].x, &a[0].y, &a[2].x, &a[2].y);
sc("%lld%lld%lld%lld", &b[0].x, &b[0].y, &b[2].x, &b[2].y);
x[0] = a[0].x; x[1] = a[2].x; x[2] = b[0].x; x[3] = b[2].x;
y[0] = a[0].y; y[1] = a[2].y; y[2] = b[0].y; y[3] = b[2].y;
sort(x, x + 4);
a[0].x = lower_bound(x, x + 4, a[0].x) - x + 1;
a[2].x = lower_bound(x, x + 4, a[2].x) - x + 1;
b[0].x = lower_bound(x, x + 4, b[0].x) - x + 1;
b[2].x = lower_bound(x, x + 4, b[2].x) - x + 1;
sort(y, y + 4);
a[0].y = lower_bound(y, y + 4, a[0].y) - y + 1;
a[2].y = lower_bound(y, y + 4, a[2].y) - y + 1;
b[0].y = lower_bound(y, y + 4, b[0].y) - y + 1;
b[2].y = lower_bound(y, y + 4, b[2].y) - y + 1;
// a[0].print();
// a[2].print();
// b[0].print();
// b[2].print();
a[1] = point{ a[0].x,a[2].y };
a[3] = point{ a[2].x,a[0].y };
b[1] = point{ b[0].x,b[2].y };
b[3] = point{ b[2].x,b[0].y };
for (int i = 0; i < 4; i++)
{
calc(a[i], a[(i + 1) % 4]);
calc(b[i], b[(i + 1) % 4]);
}
/*for (int i = 1; i <= 25; i++)
for (int j = 1; j <= 25; j++)
printf("%d%c", s[i][j], j == 25 ? '\n' : ' ');*/
memset(vis, false, sizeof(vis));
int color = 0;
for (int i = 1; i <= 25; ++i) {
if (!vis[i]) {
++color;
vis[i] = true;
dfs(i);
}
}
printf("%d\n", color);
}
} 666 Quailty and CCPC
签到
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 1e5 + 5;
struct node
{
char s[15];
int num;
int pat;
}que[100005];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n, d;
sc("%d%d", &n, &d);
for (int i = 0; i < n; i++)
sc("%s%d%d", que[i].s, &que[i].num, &que[i].pat);
sort(que, que + n, [](node q, node w) {
if (q.num != w.num)
return q.num > w.num;
return q.pat < w.pat;
});
ll qq = (ll)n * d;
if (qq % 10 != 5)
pr("Quailty is very great\n");
else
{
qq = qq / 10 + 1;
printf("%s\n", que[qq - 1].s);
}
}
} 6667 Roundgod and Milk Tea
有 n 个班，每个班的人数和茶都不相同，每个班的人不能喝自己班的茶，问最多有多少个人能喝茶
贪心，枚举班，这个班不喝自己的茶的能喝的最大的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sc scanf
#define pr printf
const int N =1e6 + 10;
ll a[N], b[N];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
ll sum = 0;
for (int i = 1; i <= n; i++)
{
sc("%lld %lld", &a[i], &b[i]);
sum += b[i];
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ll t = sum - b[i];
ll t1;
if (ans > b[i])
t1 = ans - b[i];
else
t1 = 0;
t -= t1;
ans += min(a[i], t);
}
printf("%lld\n", ans);
}
}
京公网安备 11010502036488号