alextang

650

BlizzardWasteland
sduwhacm03

alextang
2个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define fi first
#define se second
#define mp make_pair
const int N = 1e5 + 10;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
LL powmod(LL a,LL b,LL mod) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
LL gcd(LL a,LL b) { return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b) { return a*b/gcd(a,b);}

int main(){
int T;cin >> T;
while (T--){
int n,m;
cin >> n >> m;
int res = 0,cur = 0;
while (n--){
int x;cin >> x;
if (x + cur > m)    res++,cur = 0;
cur += x;
}
if (cur)    res++;
cout << res << endl;
}
return 0;
}



alextang
2个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 2e5 + 50;
int n;
int in[N],out[N];
bool vis[N];

int main(){
int T;cin >> T;
while (T--){
cin >> n;
memset(vis,0,sizeof vis);
memset(in,0,sizeof in);
memset(out,0,sizeof out);
for (int i = 1;i <= n;++i){
cin >> out[i];
in[out[i]] = i;
}
bool f = 0;
for (int i = 1;i <= n;++i){
if (vis[i] || !out[i])  continue;
vis[i] = true;
int head = i,tail = i;
}
while (in[tail] && !vis[in[tail]]){
tail = in[tail];
vis[tail] = 1;
}
if (!f){
f = 1;
for (int j = 1;j <= n;++j){
if (!in[j] && !out[j]){
vis[j] = 1;
}
}
}
}
if (!f){
int x = 0,y = 0;
for (int i = 1;i <= n;++i){
if (!out[i])
{
if (!x && !y)   x = y = i;
else{
out[x] = i;
x = i;
}
}
}
out[x] = y;
}
for (int i = 1;i <= n;++i){
printf("%d ",out[i]);
}
puts("");
}
return 0;
}


alextang
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 220;
int n;
void update(char &c){
if (c == 'W') c = 'B';
else c = 'W';
}

bool check(string s,char c){
vector<int> step;
for (int i = 0;i < n - 1;++i){
if (s[i] != c){
step.push_back(i+1);
update(s[i]);
update(s[i+1]);
}
}
if (s.back() != s[0])   return false;
cout << step.size() << endl;
for (auto x: step)  cout << x << ' ';
if (step.size()) cout << endl;
return true;
}

int main(){
int T;cin >> T;
while (T--){
string s;
cin >> n >> s;
if (!check(s,'W') && !check(s,'B')) puts("-1");
}
return 0;
}


alextang
2个月前
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
int T;cin >> T;
while (T--){
int a,b,c,d,e,f;
cin >> a >> b >> c >> d >> e >> f;
int res = 0;
if (e >= f){
res += min(a,d) * e;
d -= min(a,d);
res += f * min(b,min(c,d));
}else{
res += min(b,min(c,d)) * f;
d -= min(b,min(c,d));
res += e * min(a,d);
}
printf("%d\n",res);
}
return 0;
}


alextang
2个月前
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
int T;scanf("%d",&T);
while (T--){
int n,x;
scanf("%d%d",&n,&x);
bool f = 0;
int a = 0;
while (n--){
int b;scanf("%d",&b);
if (b == x) f = 1;
a = max(a,b);
}
//cout << "asdasdas:" << a << endl;
if (f)  puts("1");
else if (a > x) puts("2");
else printf("%d\n",(x+a-1) / a);
}
return 0;
}


alextang
11个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res;
res.push_back(1);
for (int i = 2; i <= N;++i){
int l = 0,r = res.size()-1;
while (l <= r){
int mid = (l + r) >> 1;
if (compare(res[mid],i)) l = mid + 1;
else    r = mid - 1;
}
// r l
res.push_back(i);
for (int i = res.size() - 2;i >= l;--i) swap(res[i+1],res[i]);
}
return res;
}
};


alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
double a[N],b[N],s[N];
int n,L;
bool check(){
double ans = -INF;
double minn = INF;
for (int i = L;i <= n;++i){
minn = min(minn,s[i-L]);
ans = max(ans,s[i] - minn);
}
return ans >= 0;
}
int main(){
cin >> n >> L;
for (int i = 1;i <= n;++i){
scanf("%lf",&a[i]);
}
double l = 1e-6,r = 1e6;
while (r - l > eps){
double mid = (r + l) / 2;
for (int i = 1;i <= n;++i){
b[i] = a[i] - mid;
}
for (int i = 1;i <= n;++i){
s[i] = s[i-1] + b[i];
}
if (check())    l = mid;
else    r = mid;
}
cout << int(r * 1000) << endl;
return 0;
}


alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
int n,p,h,m;
const int maxn = 1e4 + 5;
map<pair<int,int>,bool> vis;
int d[maxn];
int c[maxn];
int main(){
cin >> n >> p >> h >> m;
for (int i = 0;i < m;++i){
int a,b;cin >> a >> b;
if (a > b)  swap(a,b);
if (vis[make_pair(a,b)])    continue;
d[a+1]--;d[b]++;
vis[make_pair(a,b)] = 1;
}
//c[1] = d[1];
for (int i = 1;i <= n ;++i){
c[i] = c[i-1] + d[i];
cout << c[i] + h << endl;
}
return 0;
}


alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5  +5;
int a[maxn];
int n;
int main(){
scanf("%d",&n);
for (int i = 1;i <= n;++i){
scanf("%d",&a[i]);
}
for (int i = n;i > 1;--i){
a[i] -= a[i-1];
}
long long pos = 0;
long long neg = 0;
for (int i = 2;i <= n;++i){
if (a[i] > 0)   pos += a[i];
else if (a[i] < 0)  neg -= a[i];
}
cout << min(pos,neg) + abs(pos-neg) << endl;
cout << abs(pos-neg) + 1 << endl;
return 0;
}


alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int g[maxn][maxn];
int main(){
int N,r;cin >> N >> r;
r = min(5001,r);
int n = 5001,m = 5001;
for (int i = 0,x,y,w;i < N;++i){
cin >> x >> y >> w;
x++;y++;
g[x][y] += w;
}
for (int i = 1;i <= n;++i){
for (int j = 1;j <= m;++j){
g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
}
}
int res = 0;
for (int i = r;i <= n;++i){
for (int j = r;j <= m;++j){
res = max(res,g[i][j] - g[i-r][j] - g[i][j-r] + g[i-r][j-r]);
}
}
cout << res << endl;
return 0;
}