# “蔚来杯”2022牛客暑期多校训练营4()-其他

## “蔚来杯”2022牛客暑期多校训练营4()

https://ac.nowcoder.com/acm/contest/33189

A.Task Computing

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n, m;
cin >> n >> m;
vector < array<LL, 2> > a(n);
for (int i = 0; i < n; i ++ )
cin >> a[i][0];
for (int i = 0; i < n; i ++ )
cin >> a[i][1];
sort(a.begin(), a.end(), [&](auto x, auto y){
return x[0] * (10000 - y[1]) < y[0] * (10000 - x[1]);
});
vector <double> dp(m + 1);
for (int i = 0; i < n; i ++ ){
for (int j = m; j >= 1; j -- ){
dp[j] = max(dp[j], dp[j - 1] * 0.0001 * a[i][1] + a[i][0]);
}
}
cout << fixed << setprecision(15) << dp[m] << "\n";
return 0;
}


D.Jobs (Easy Version)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 998244353;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n, q;
cin >> n >> q;
vector dp(n, vector(401, vector<LL>(401, 401)));
for (int i = 0; i < n; i ++ ){
LL m;
cin >> m;
for (int j = 0; j < m; j ++ ){
LL a, b, c;
cin >> a >> b >> c;
dp[i][a][b] = min(dp[i][a][b], c);
}
for (int a = 1; a <= 400; a ++ )
for (int b = 1; b <= 400; b ++ ){
dp[i][a][b] = min(dp[i][a][b], dp[i][a - 1][b]);
dp[i][a][b] = min(dp[i][a][b], dp[i][a][b - 1]);
}
}
LL seed;
cin >> seed;
mt19937 rng(seed);
uniform_int_distribution<> u(1, 400);
auto solve = [&](LL a, LL b, LL c){
LL ans = 0;
for (int i = 0; i < n; i ++ )
ans += (c >= dp[i][a][b]);
return ans;
};
LL lastans = 0, ans = 0;
for (int i = 1; i <= q; i ++ ){
LL IQ = (u(rng) ^ lastans) % 400 + 1;
LL EQ = (u(rng) ^ lastans) % 400 + 1;
LL AQ = (u(rng) ^ lastans) % 400 + 1;
lastans = solve(IQ, EQ, AQ);
ans = (ans * seed + lastans) % mod;
}
cout << ans << "\n";
return 0;
}


H.Wall Builder II

#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
LL n;
cin >> n;
LL area = 0;
for (int i = 1; i <= n; i ++ )
area += i * (n - i + 1);
LL ans = 1e9;
vector < vector<LL> > point(n * (n + 1) / 2);
auto check = [&](LL w, LL h){
vector < vector<LL> > t(n * (n + 1) / 2);
multiset <LL> seg;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n - i + 1; j ++ )
seg.insert(i);
LL cnt = 0;
for (int i = 0; i < h; i ++ ){
LL tw = w;
while(tw > 0){
auto it = seg.lower_bound(tw);
LL len = *it;
LL mx = *(prev(seg.end()));
if (len > mx){
len = mx;
it = prev(seg.end());
}
if (len > tw) return;
seg.erase(it);
t[cnt].push_back(w - tw);
t[cnt].push_back(i);
t[cnt].push_back(w - tw + len);
t[cnt].push_back(i + 1);
cnt ++ ;
tw -= len;
}
}
ans = min(ans, 2 * (w + h));
for (int i = 0; i < n * (n + 1) / 2; i ++ )
point[i] = t[i];
};
for (int w = 1; w <= area / w; w ++ ){
if (area % w == 0){
check(w, area / w);
check(area / w, w);
}
}
cout << ans << "\n";
for (int i = 0; i < n * (n + 1) / 2; i ++ )
for (int j = 0; j < 4; j ++ )
cout << point[i][j] << " \n"[j == 3];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}


K.NIO’s Sword

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL fac[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n;
cin >> n;
if (n == 1){
cout << "0\n";
}
else{
LL ans = 0;
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= 6; j ++ ){
LL x = (i - fac[j] * (i - 1) % n + n) % n;
if (x < fac[j]){
ans += j;
break;
}
}
}
cout << ans << "\n";
}
return 0;
}


N.Particle Arts

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n;
cin >> n;
vector <LL> a(n), bit(20);
for (int i = 0; i < n; i ++ ){
cin >> a[i];
LL cnt = 0;
while(a[i]){
bit[cnt ++ ] += (a[i] & 1);
a[i] >>= 1;
}
}
LL sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i ++ ){
for (int j = 15; j >= 0; j -- ){
a[i] <<= 1;
if (bit[j]){
a[i] ++ ;
bit[j] -- ;
}
}
sum1 += a[i];
sum2 += a[i] * a[i];
}
LL p = sum2 * n - sum1 * sum1;
LL q = n * n;
LL g = gcd(p, q);
cout << p / g << "/" << q / g << "\n";
return 0;
}

————————

https://ac.nowcoder.com/acm/contest/33189

A.Task Computing

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n, m;
cin >> n >> m;
vector < array<LL, 2> > a(n);
for (int i = 0; i < n; i ++ )
cin >> a[i][0];
for (int i = 0; i < n; i ++ )
cin >> a[i][1];
sort(a.begin(), a.end(), [&](auto x, auto y){
return x[0] * (10000 - y[1]) < y[0] * (10000 - x[1]);
});
vector <double> dp(m + 1);
for (int i = 0; i < n; i ++ ){
for (int j = m; j >= 1; j -- ){
dp[j] = max(dp[j], dp[j - 1] * 0.0001 * a[i][1] + a[i][0]);
}
}
cout << fixed << setprecision(15) << dp[m] << "\n";
return 0;
}


D.Jobs (Easy Version)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 998244353;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n, q;
cin >> n >> q;
vector dp(n, vector(401, vector<LL>(401, 401)));
for (int i = 0; i < n; i ++ ){
LL m;
cin >> m;
for (int j = 0; j < m; j ++ ){
LL a, b, c;
cin >> a >> b >> c;
dp[i][a][b] = min(dp[i][a][b], c);
}
for (int a = 1; a <= 400; a ++ )
for (int b = 1; b <= 400; b ++ ){
dp[i][a][b] = min(dp[i][a][b], dp[i][a - 1][b]);
dp[i][a][b] = min(dp[i][a][b], dp[i][a][b - 1]);
}
}
LL seed;
cin >> seed;
mt19937 rng(seed);
uniform_int_distribution<> u(1, 400);
auto solve = [&](LL a, LL b, LL c){
LL ans = 0;
for (int i = 0; i < n; i ++ )
ans += (c >= dp[i][a][b]);
return ans;
};
LL lastans = 0, ans = 0;
for (int i = 1; i <= q; i ++ ){
LL IQ = (u(rng) ^ lastans) % 400 + 1;
LL EQ = (u(rng) ^ lastans) % 400 + 1;
LL AQ = (u(rng) ^ lastans) % 400 + 1;
lastans = solve(IQ, EQ, AQ);
ans = (ans * seed + lastans) % mod;
}
cout << ans << "\n";
return 0;
}


H.Wall Builder II

#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
LL n;
cin >> n;
LL area = 0;
for (int i = 1; i <= n; i ++ )
area += i * (n - i + 1);
LL ans = 1e9;
vector < vector<LL> > point(n * (n + 1) / 2);
auto check = [&](LL w, LL h){
vector < vector<LL> > t(n * (n + 1) / 2);
multiset <LL> seg;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n - i + 1; j ++ )
seg.insert(i);
LL cnt = 0;
for (int i = 0; i < h; i ++ ){
LL tw = w;
while(tw > 0){
auto it = seg.lower_bound(tw);
LL len = *it;
LL mx = *(prev(seg.end()));
if (len > mx){
len = mx;
it = prev(seg.end());
}
if (len > tw) return;
seg.erase(it);
t[cnt].push_back(w - tw);
t[cnt].push_back(i);
t[cnt].push_back(w - tw + len);
t[cnt].push_back(i + 1);
cnt ++ ;
tw -= len;
}
}
ans = min(ans, 2 * (w + h));
for (int i = 0; i < n * (n + 1) / 2; i ++ )
point[i] = t[i];
};
for (int w = 1; w <= area / w; w ++ ){
if (area % w == 0){
check(w, area / w);
check(area / w, w);
}
}
cout << ans << "\n";
for (int i = 0; i < n * (n + 1) / 2; i ++ )
for (int j = 0; j < 4; j ++ )
cout << point[i][j] << " \n"[j == 3];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}


K.NIO’s Sword

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL fac[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n;
cin >> n;
if (n == 1){
cout << "0\n";
}
else{
LL ans = 0;
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= 6; j ++ ){
LL x = (i - fac[j] * (i - 1) % n + n) % n;
if (x < fac[j]){
ans += j;
break;
}
}
}
cout << ans << "\n";
}
return 0;
}


N.Particle Arts

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n;
cin >> n;
vector <LL> a(n), bit(20);
for (int i = 0; i < n; i ++ ){
cin >> a[i];
LL cnt = 0;
while(a[i]){
bit[cnt ++ ] += (a[i] & 1);
a[i] >>= 1;
}
}
LL sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i ++ ){
for (int j = 15; j >= 0; j -- ){
a[i] <<= 1;
if (bit[j]){
a[i] ++ ;
bit[j] -- ;
}
}
sum1 += a[i];
sum2 += a[i] * a[i];
}
LL p = sum2 * n - sum1 * sum1;
LL q = n * n;
LL g = gcd(p, q);
cout << p / g << "/" << q / g << "\n";
return 0;
}