DS_Tape

941

fushi2218
thisdoubi
YikN
lcyzoi

R.G莎
BstIsYettoCom
TralSun

uzimaki

ji_suan_ji

Tom12

DS_Tape
23小时前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int n;
int a[N];
int Left[N][N], Right[N][N];

int main(){
int T;
cin >> T;
while(T--){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int len = 1; len <= n; len++)
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
if(l == r) Left[l][r] = Right[l][r] = a[l];
else{
int L = Left[l][r - 1], R = Right[l][r - 1], X = a[r];
int &yl = Left[l][r];
if(X == R) yl = 0;
else if(X < R && X <= L || R < X && L <= X) yl = X;
else if(L < R) yl = X + 1;
else yl = X - 1;

L = Left[l + 1][r], R = Right[l + 1][r], X = a[l];
int &yr = Right[l][r];
if(X == L) yr = 0;
else if(X <= R && X < L || R <= X && L < X) yr = X;
else if(L > R) yr = X + 1;
else yr = X - 1;
}
}
if(n == 1) cout << 1 << endl;
else printf("%d\n", a[1] != Left[2][n]);
}
}


DS_Tape
23小时前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 55, M = N * 1000;

int n;
int f[N][M];

bool dfs(int a, int b){
int &v = f[a][b];
if(v != -1) return v;
if(b == 1) return dfs(a + 1, 0);
if(!a) return v = b & 1;

if(a && !dfs(a - 1, b)) return v = 1;
if(b && !dfs(a, b - 1)) return v = 1;
if(a >= 2 && !dfs(a - 2, b + (b ? 3 : 2))) return v = 1;
if(a && b && !dfs(a - 1, b + 1)) return v = 1;

return v = 0;
}
int main(){
int T;
cin >> T;
memset(f, -1, sizeof f);
while(T--){
cin >> n;
int a = 0, b = 0;
for(int i = 0; i < n; i++){
int x;
cin >> x;
if(x == 1) a++;
else b += x;
}
b += n - a - 1;
if(dfs(a, b)) puts("YES");
else puts("NO");
}
}


DS_Tape
1天前

DS_Tape
1天前
#include<iostream>
#include<cmath>

using namespace std;

const int N = 2e5 + 10;

int n, m;
int f[N][20];

void init(){
for(int j = 1; j < 18; j++)
for(int i = 1; i + (1 << j) <= n + 1; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r){
int k = log(r - l + 1) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> f[i][0];
init();
cin >> m;
while(m--){
int l, r;
cin >> l >> r;
cout << query(l, r) << endl;
}
return 0;
}


DS_Tape
1天前
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<set>
using namespace std;

const int N = 1e6;
long long a[N], tmp[N];
long long mergesort(int l,int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
long long cnt = mergesort(l, mid) + mergesort(mid + 1, r);
int st1 = l, st2 = mid + 1;
for (int i = l; i <= r; i++) {
if (st1 <= mid && a[st1] < a[st2] || st2 > r)
tmp[i] = a[st1++];
else {
tmp[i] = a[st2++];
cnt += mid - st1 + 1;
}
}
for (int i = l; i <= r; i++)
a[i] = tmp[i];
return cnt;
}
int main() {
int n;
while (cin >> n, n) {
for (int i = 0; i < n; i++)
cin >> a[i];
cout << mergesort(0, n - 1) << endl;
}

return 0;
}


DS_Tape
1天前
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<set>
using namespace std;

const int N = 1e5 + 4;

priority_queue<int> a;
priority_queue<int, vector<int>, greater<int>> b;

void ins(int x) {
b.push(x);
if (b.size() > a.size()) {
a.push(b.top());
b.pop();
}
while (a.size() && b.size() && a.top() > b.top()) {
b.push(a.top());
a.pop();
a.push(b.top());
b.pop();
}
}
int getmid() {
return a.top();
}
int p[N];
int main() {
int t;
cin >> t;
while (t--) {
int x, m;
cin >> x >> m;
for (int i = 1; i <= m; i++)
cin >> p[i];

cout << x << ' ' << (m + 1) / 2 << endl;
int k = 0;
for (int i = 1; i <= m; i++) {
k++;
ins(p[i]);
if (i & 1) cout << getmid() << ' ';
if (k % 20 == 0) cout << endl;
}
if (k % 20) cout << endl;
while (a.size()) a.pop();
while (b.size()) b.pop();
}

return 0;
}


DS_Tape
1天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, m, T;
int col[N], row[N];
int sum[N];
LL make(int n, int p[]){
if(T % n) return -1;
int ave = T / n;
LL res = 0;
for(int i = 1; i <= n; i++) p[i] -= ave;
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + p[i];

sort(sum + 1, sum + n + 1);
int mid = 1 + n >> 1;
for(int i = 1; i <= n; i++) res += abs(sum[mid] - sum[i]);
return res;
}
int main(){
cin >> n >> m >> T;
for(int i = 0; i < T; i++){
int x, y;
cin >> x >> y;
row[x]++;
col[y]++;
}
LL ans1 = make(n, row), ans2 = make(m, col);
if(ans1 != -1 && ans2 != -1) printf("both %lld\n", ans1 + ans2);
else if(ans2 != -1) printf("column %lld\n", ans2);
else if(ans1 != -1) printf("row %lld\n", ans1);
else puts("impossible");
return 0;
}


DS_Tape
1天前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N = 2010, M = 6010;

int n, m, k;
int h[N], e[M], ne[M], idx;
int sg[N];
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u){
if(sg[u] != -1) return sg[u];

unordered_set<int> map;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
map.insert(dfs(j));
}
for(int i = 0;; i++)
if(!map.count(i)) return sg[u] = i;
}
int main(){
cin >> n >> m >> k;
memset(h, -1, sizeof h);
memset(sg, -1, sizeof sg);
while(m--){
int a, b;
cin >> a >> b;
}
int res = 0;
for(int i = 0; i < k; i++){
int x;
cin >> x;
res ^= dfs(x);
}
if(res) puts("win");
else puts("lose");
return 0;
}


DS_Tape
1天前
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
using namespace std;

typedef long long LL;
pair<LL, LL> trans(LL z,int n) {
LL x, y;
if (n == 1) {
if (z == 1) x = 1, y = 1;
if (z == 2) x = 1, y = 2;
if (z == 3) x = 2, y = 2;
if (z == 4) x = 2, y = 1;
return pair<LL, LL>(x, y);
}
LL len = 1LL << (n - 1);
LL lenn = 1LL << 2 * n - 2;
int k = z - 1 >> 2 * n - 2;
auto p = trans((z - 1) % lenn + 1, n - 1);
switch (k){
case 0:
x = p.second;
y = p.first;
break;
case 1:
x = p.first;
y = p.second + len;
break;
case 2:
x = p.first + len;
y = p.second +len;
break;
case 3:
x = 2*len - p.second + 1;
y = len - p.first + 1;
break;
default:
break;
}
return pair<LL, LL>(x, y);
}
int main() {
int t;
cin >> t;
while (t--) {
LL n, a, b;
cin >> n >> a >> b;
auto A = trans(a, n);
auto B = trans(b, n);
LL dx = A.first - B.first;
LL dy = A.second - B.second;
double k = sqrt((dx * dx + dy * dy)) * 10;
printf("%.0lf\n", k);
}
return 0;
}


DS_Tape
1天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 5e3 + 10;
int s[N][N];

int main(){
int n, r;
cin >> n >> r;
int down = 0, right = 0;
for(int i = 0; i < n; i++){
int x, y, w;
cin >> x >> y >> w;
s[++x][++y] += w;
if(x > down) down = x;
if(y > right) right = y;
}
for(int i = 1; i <= down; i++)
for(int j = 1; j <= right; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
int res = 0;
for(int i = 1; i <= down; i++)
for(int j = 1; j <= right; j++){
int x1 = max(0, i - r);
int y1 = max(0, j - r);
res = max(res, s[i][j] - s[i][y1] - s[x1][j] + s[x1][y1]);
}

cout << res << endl;
return 0;
}