D： Defuse the Bombs
有n个计数器，初值为$a_i$，每秒钟可以将一个计数器的值+1，然后所有的计数器的值-1。问最多几秒后所有计数器的最小值$\lt 0$$n\leq 10^5, 0 \leq a_i \leq 10^9$
做法
转化一下问题：每秒钟可以让一个计数器值+1，第i秒钟要求所有计数器的值$\geq i$，问第几秒后不满足。假如第x秒钟满足条件，则要满足$sum_p+x \geq x*p$，其中$a_p$为小于x的最大的p。先枚举$a_i$，找到第一个不满足的，那么答案就是$\frac{sum_i}{i-1}+1$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int n, a[N];
ll sum[N];
void solve(int kase)
{
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
sort(a+1, a+n+1);
for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
cout << "Case #" << kase << ": ";
ll p = 0;
for(int i=1; i<=n; i++)
{
if(1ll*i*a[i]-sum[i]>a[i]) break;
p = i;
}
cout << sum[p]/(p-1)+1 << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _; cin >> _;
for(int kase=1; kase<=_; kase++) solve(kase);
return 0;
}
|
K Knowledge is Power
给定数x，要求将其分解成若干大于1的数，要求满足两两互质且和为x。最小化这些数的最大值和最小值的差值。$5 \leq x \leq 10^9$
做法
x为奇数，显然$2\frac{x-1}{2}, \frac{x+1}{2}$最优，为1考虑x为偶数：x=6无解x=8，分成3和5即可（我一开始误判成无解）通过打表得到答案只可能是2，3，4x是3的倍数，显然可以分成y, y+1, y+2的形式，又由于y一定是奇数，所以合法，答案为2$x%3==1$，如果能分成互质的y, y+1, y+3则为3，否则为4$x%3==2$，如果能分成互质的y, y+2, y+3则为3，否则为4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
void solve(int kase)
{
int x; cin >> x;
cout << "Case #" << kase << ": ";
if(x==6) cout << -1 << '\n';
else if(x&1) cout << 1 << '\n';
else
{
if(x%3==0) cout << 2 << '\n';
else if(__gcd(x/2-1, x/2+1)==1) cout << 2 << '\n';
else
{
bool ok = 0;
if(x%3==2)
{
int a = (x-5)/3, b = a+2, c = a+3;
if(__gcd(a, b)==1 && __gcd(a, c)==1 && __gcd(b, c)==1) ok = 1;
}
if(x%3==1)
{
int a = (x-4)/3, b = a+1, c = a+3;
if( __gcd(a, b)==1 && __gcd(a, c)==1 && __gcd(b, c)==1) ok = 1;
}
if(ok) cout << 3 << '\n';
else cout << 4 << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _; cin >> _;
for(int k=1; k<=_; k++) solve(k);
return 0;
}
|
J Joy of Handcraft
有n个灯泡，分别有周期$t_i$，每两个周期中，前一个周期亮，后一个周期暗，有亮度$x_i$。问1-m每个时间内的最大亮度$n \leq 10^5, m \leq 10^5, t_i \leq 10^5, x_i \leq 10^5$
做法
周期相同的只要取亮度最大的那个，然后暴力枚举每种周期的灯泡亮的时间，复杂度是$O(n\log n)$，注意到将亮度排序后，就是个区间覆盖问题了，线段树即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int cov[N<<2];
void push(int p)
{
cov[p<<1] = cov[p<<1|1] = cov[p];
cov[p] = 0;
}
void cover(int p, int l, int r, int x, int y, int v)
{
if(l>=x && r<=y)
{
cov[p] = v;
return;
}
if(cov[p]) push(p);
int mid = (l+r)>>1;
if(x<=mid) cover(p<<1, l, mid, x, y, v);
if(y>mid) cover(p<<1|1, mid+1, r, x, y, v);
}
void print(int p, int l, int r)
{
if(l==r) { cout << cov[p] << " \n"[l==m]; return; }
if(cov[p]) push(p);
int mid = (l+r)>>1;
print(p<<1, l, mid); print(p<<1|1, mid+1, r);
}
void solve(int kase)
{
cin >> n >> m;
for(int i=1; i<=4*m; i++) cov[i] = 0;
vector<pair<int, int>> lamb(n);
for(auto &it : lamb) cin >> it.first >> it.second;
sort(begin(lamb), end(lamb));
vector<pair<int, int>> tmp;
for(int i=0; i<(int)lamb.size(); )
{
int j = i + 1;
while(j<(int)lamb.size() && lamb[j].first==lamb[i].first) ++j;
tmp.push_back({lamb[j-1].second, lamb[j-1].first});
i = j;
}
sort(begin(tmp), end(tmp));
for(auto it : tmp)
for(int k=1; k<=m; k+=2*it.second) cover(1, 1, m, k, min(m, k+it.second-1), it.first);
cout << "Case #" << kase << ": ";
print(1, 1, m);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _; cin >> _;
for(int k=1; k<=_; k++) solve(k);
return 0;
}
|
L Lottery
有n种石头，第i种石头体积为$2^{a_i}$，数量为$x_i$，问能拼成的体积数量。$n \leq 10^5, a_i, x_i \leq 10^9$
做法
按照体积从小到大考虑设当前枚举到第i块石头，前$i-1$块石头(前mx的体积中)不能拼成的体积为ans，前$2^{a_{i-1}}$的体积中有delta个不能被拼成，之前所有石头能拼成的最大体积为$mx$。$mx\geq 2^{a_i}$：那么对于$2^{a_{i-1}}$到$2^{a_i}$之间，每$2^{a_{i-1}}$个就有delta个体积不能被拼成。因此$\leq 2^{a_i}$的体积中不能拼成的体积的数量就是$2^{a_i-a_{i-1}}\times delta$，前i块石头不能拼成的体积就要增加$delta\times x_i$个$mx\lt 2^{a_i}$：那么$mx+1$到$2^{a_i}-1$之间的体积就无法拼成前$2^{a_{i}}$的体积中有$ans+2^{a_i}-mx-1$不能被拼成前i块石头不能拼成的体积增加$delta\times x_i$个
由于有取模操作，不能直接判断$mx$和$2^{a_i}$的大小关系，用一个map来存储mx的二进制表示即可，只要mx的二进制中最高位high$\geq a_i$，就说明$mx \geq 2^{a_i}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
int n;
pair<int, int> p[N];
int Pow(int a, int b)
{
int ans = 1;
while(b)
{
if(b&1) ans = 1ll*ans*a%mod;
a = 1ll*a*a%mod;
b >>= 1;
}
return ans;
}
void solve(int kase)
{
cin >> n;
for(int i=1; i<=n; i++) cin >> p[i].fi >> p[i].se;
map<int, int> bit;
sort(p+1, p+n+1);
int mx = 0, delta = 0, ans = 0, high = -1;
for(int i=1; i<=n; i++)
{
int cur = Pow(2, p[i].fi);
if(high>=p[i].fi)
{
delta = 1ll*delta*Pow(2, p[i].fi-p[i-1].fi)%mod;
}
else
{
delta = ((cur-mx-1+ans)%mod+mod)%mod;
}
ans = (ans + 1ll*delta*p[i].se)%mod;
mx = (mx + 1ll*cur*p[i].se)%mod;
for(int j=0; j<30; j++)
if((p[i].se>>j)&1)
{
int x = p[i].fi + j;
bit[x]++;
while(bit[x]==2)
{
bit[x] = 0;
++x;
bit[x]++;
}
high = max(high, x);
}
}
cout << "Case #" << kase << ": ";
cout << ((mx - ans + 1)%mod+mod)%mod << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _; cin >> _;
for(int k=1; k<=_; k++) solve(k);
return 0;
}
|
G Game of Cards
有$c_0$个0号牌，$c_1$个1号牌，$c_2$个2号牌，$c_3$个3号牌，每次操作可以选取两张和不超过3的牌，然后将这两张牌换成一张它们的和的号的牌，不能操作者输。$0\leq c_0,c_1,c_2, c_3\leq 10^9$
做法
简单分析一下：3号牌只能和0号牌组合，且只会增加不会减少，影响到局面的就是3号牌有还是没有。如果操作0号牌，每次必然会减少1，所以0号牌影响局面的是它的奇偶性。然后只需要对1和2的数目以及3号牌是0还是1，0号牌是奇数还是偶数打个sg表即可。发现只有0号牌时，需要特判。此外3号牌没有影响。0号牌有偶数个时，2号牌为0和非0时，1号牌模3各有一个规律0号牌有奇数个时，2号牌为0和1和>1时，1号牌模3各有一规律if else一下即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
using namespace std;
void win() { cout << "Rabbit\n"; }
void lose() { cout << "Horse\n"; }
void solve(int kase)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << "Case #" << kase << ": ";
bool ok = 0;
if(a%2==0)
{
if(!c)
{
if(b%3==2) ok = 1;
else ok = 0;
}
else
{
if(b%3==0) ok = 0;
else ok = 1;
}
}
else
{
if(!c)
{
if(b%3==2) ok = 0;
else ok = 1;
}
else if(c==1)
{
if(b%3==0) ok = 1;
else ok = 0;
}
else
{
if(b%3==1) ok = 0;
else ok = 1;
}
}
if(!b&&!c&&!d)
{
if(a<=1) ok = 0;
else if(a&1) ok = 0;
else ok = 1;
}
ok ? win() : lose();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _; cin >> _;
for(int k=1; k<=_; k++) solve(k);
return 0;
}
|