不得不说，牛客多校题目质量确实是不错的
2023-04-18 12:53:24 时间
这套牛客多校训练的题目应该是我做过所有训练题里面质量算相当高的了。
非常推荐给大家做一做。
题目链接
https://ac.nowcoder.com/acm/contest/883
Problem A
题意：定义 S(x) 表示与结点 x 相邻的点集，给出一列边。要求支持下面两个操作：
- 将一个区间的边状态置反（本来存在的删除，本来删除的加上）；
- 判断 S(x) 和 S(y) 是否相同。
题解：一个我不太知道的套路：边集 S(x) 可以用一个整数来表示，我们通过给每个点一个随机的权值，然后将点集里面的点权值异或起来得到 S(x) 。然后维护的话，考虑把边序列分块。
每次修改操作，可以变成两边块单点修改，中间的块，记录一下当前整个块的状态。
查询的时候，每个点的 S(x) ，就是单点的状态和相关块状态的异或，判断两个 S 是否相等即可。
所以需要预处理每个块与相关联点的抑或。
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int maxn=210010;
int T,n,m;
ULL key[maxn],s[maxn],block[maxn],bs[510][maxn],tag[510];
struct edge
{
int x,y;
}e[maxn];
int main()
{
scanf("%d",&T);
for (int i=1;i<=100000;i++)
key[i]=(ULL)rand()*4000000+rand()+1;
while(T--)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
s[i]=0;
int limit=(int)sqrt((double)m);
int blocks=(m-1)/limit+1;
for (int i=1;i<=blocks;i++)
{
tag[i]=1;
for (int j=1;j<=n;j++)
bs[i][j]=0;
}
int num=0;blocks=1;
for (int i=1;i<=m;i++)
{
scanf("%d%d",&e[i].x,&e[i].y);
num++;
if (num>limit) num-=limit,blocks++;
block[i]=blocks;
bs[block[i]][e[i].x]^=key[e[i].y];
bs[block[i]][e[i].y]^=key[e[i].x];
}
// for (int i=1;i<=limit+1;i++)
// for (int j=1;j<=n;j++)
// printf("bs[%d][%d]=%llu
",i,j,bs[i][j]);
for (int i=1;i<=blocks;i++)
tag[i]=1;
int q,x,y,z;
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d",&x,&y,&z);
if (x==1)
{
int l=block[y],r=block[z];
for (int i=l+1;i<=r-1;i++)
tag[i]^=1;
if (l==r)
{
for (int i=y;i<=z;i++)
s[e[i].x]^=key[e[i].y],
s[e[i].y]^=key[e[i].x];
}
else
{
l=l*limit;r=(r-1)*limit+1;
for (int i=y;i<=l;i++)
s[e[i].x]^=key[e[i].y],
s[e[i].y]^=key[e[i].x];
for (int i=r;i<=z;i++)
s[e[i].x]^=key[e[i].y],
s[e[i].y]^=key[e[i].x];
}
}
else
{
ULL ansx=s[y],ansy=s[z];
for (int i=1;i<=blocks;i++)
if (tag[i])
ansx^=bs[i][y],ansy^=bs[i][z];
if (ansx==ansy) putchar('1');else putchar('0');
}
}
puts("");
}
return 0;
}
Problem B
题意：求 0/1 数列中包含 0/1 数量相等的最长子串和子序列。
题意：子序列，显然就是尽可能多得找 0/1 ，那么答案就是 0/1 数量 min 的两倍。对于子串，如果一个子串的 0/1 数量相等的话，那么他们前缀和相等，前缀和以后，处理相同数的最远位置就好了。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,m,sum[100010];
char s[100010];
map<int,int> Min,Max;
int main()
{
scanf("%d%s",&n,s+1);
memset(sum,0,sizeof(sum));
int zero=0,one=0;Min[0]=0;Max[0]=0;
for (int i=1;i<=n;i++)
{
if (s[i]=='0') sum[i]=sum[i-1]-1,zero++;
else sum[i]=sum[i-1]+1,one++;
if (Min.find(sum[i])==Min.end()) Min[sum[i]]=i;
Max[sum[i]]=i;
//cout<<i<<" "<<sum[i]<<endl;
}
int ans=0;
for (auto i:Min)
{
int x=i.first;
ans=max(Max[x]-Min[x],ans);
}
printf("%d ",ans);
ans=min(zero,one)*2;
printf("%d
",ans);
return 0;
}
Problem C
题意：给定一个首尾为 1，部分位置被删除的 ETT 序列 {a_n} ，将其还原。
题解：合法的 ETT 序列中，若 a_l=a_r ，则 a_{l+1 dots r-1} 之间出现的值不能在 a_{1 dots l-1} 和 a_{r+1 dots n} 中出现，同时可以将 a_{l dots r} 替换成 a_l 而不影响 ETT 的性质。
考虑每次将现 ETT 序列中 a_l=a_r 且 a_{l+1 dots r-1} 互不相同的段落 a_{l cdots r} 。对于其中所有被删除的位 a_p=-1 ，我们可以证明只要 a_{p-2},a_{p-1} eq -1,a[l] ，就可以将 a_p 替换成 a_{p-2} 而不影响 ETT 的性质。这个性质对 k+2 也同样生效。
在将所有满足这种条件的位置全部删除之后，我们把 a_{l+2*k} 的所有被删除的位置都填上 a_l ，再用没有出现过的元素填满剩下的空隙，就能将 a_{ldots r} 缩成一个数 a_l 。最后将 a_{1dots n} 缩点之后所有的删除位置都应该填上了值，此时的序列就是答案。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=5e5+5;
int n,m;
int a[maxn],sa,b[maxn],c[maxn];
int q[maxn],sq,e[maxn],se;
void solve(int l,int r){
int i,j,cl,t;
bool flg;
sq=-1; cl=c[a[l]];
for (i=l+1;i<r;i++){
q[++sq]=a[i];
flg=true;
while (sq>1&&flg){
flg=false;
if (c[q[sq]]==-1){
if (c[q[sq-1]]!=-1&&c[q[sq-2]]!=-1){
c[q[sq]]=c[q[sq-2]]; sq-=2;
flg=true;
}
}
else{
if (c[q[sq-1]]!=-1&&c[q[sq-2]]==-1){
c[q[sq-2]]=c[q[sq]]; sq-=2;
flg=true;
}
}
}
}
for (i=1;i<=sq;i+=2) if (c[q[i]]==-1) c[q[i]]=cl;
for (i=0;i<=sq;i+=2) if (c[q[i]]==-1){
t=e[se--]; c[q[i]]=t; j=i+2;
while (j<=sq&&c[q[j-1]]!=cl){
c[q[j]]=t; j+=2;
}
}
}
int main(){
int tt;
int i;
scanf("%d",&tt);
while (tt--){
scanf("%d",&n); m=(n<<1)-1;
for (i=1;i<=n;i++) b[i]=1;
for (i=0;i<m;i++) scanf("%d",&c[i]);
c[0]=c[m-1]=1;
for (i=m-1;i>=0;i--) b[c[i]]=0;
se=-1;
for (i=1;i<=n;i++) if (b[i]) e[++se]=i;
sa=-1;
for (i=1;i<=n;i++) b[i]=-1;
for (i=0;i<m;i++){
a[++sa]=i;
if (c[i]!=-1){
if (b[c[i]]==-1) b[c[i]]=sa;
else{
solve(b[c[i]],sa); sa=b[c[i]];
}
}
}
for (i=0;i<m;i++) printf("%d ",c[i]);
puts("");
}
return 0;
}
Problem D
题意：求出二元组的个数 (i,j) 使得 A(i^j) equiv 0 pmod{p}, (i le n, j le m) ，其中 A(i) 为 i 个数字 1 链接起来的数
题解：把数字用等比数列加起来得 frac{10^{i^j}-1}{9} equiv 0 pmod{p} ，特判 p=2，3，5 的情况，剩下的转化为求 i^jequiv 0 pmod{x} ，其中 x 是最小的正整数满足 10^x equiv 0pmod{p} 。然后再用上欧拉定理。如何计数呢，枚举 x 的素因子组成，i 必须也包含素因子。分成两种情况，一种是 x|i ，这样 j 怎么着都行，另一种考虑 dfs i 中包含 x 的素因子组成，j=cnt(n/cur) imes (m-minj+1) ，其中 cur 是 x 素因子乘起来的结果，minj 是最小的 j 使得 i^j 能整除以 x ，这个 dfs 的时候都能维护。实际上 dfs 复杂度玄学，但是能过。
由于场上分解质因数写挂了，这题没过。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define int long long
// #define zerol
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
//--------------------------------------------------------------------------------------------
const int MAXN = 1e6+5;
int prime[MAXN], pcnt;
int minp[MAXN];
struct Frac {
LL a, b;
Frac(LL a=0, LL b=0){
this->a = a;
this->b = b;
LL g = __gcd(a, b);
a /= g;
b /= g;
if (b < 0) {
a = -a;
b = -b;
}
this->a = a;
this->b = b;
}
Frac operator + (const Frac &other) {
LL newb = b * other.b;
LL newa = a * other.b + b * other.a;
return Frac(newa, newb);
}
};
void init() {
for (int i=2; i<MAXN; ++i) {
if (!minp[i]) {
prime[pcnt++] = i;
minp[i] = i;
}
for (int j=0; j<pcnt; ++j) {
LL nextp = 1LL*i*prime[j];
if (nextp >= MAXN) break;
if (!minp[nextp]) minp[nextp] = prime[j];
if (i % prime[j] == 0) {
break;
}
}
}
}
int n, p, m;
typedef pair<int, int> pii;
vector<pii> primed(int n) {
vector<pii> res;
if (n <MAXN) {
while (n > 1) {
int p = minp[n], cnt = 0;
for (; n%p==0; n/=p,++cnt);
res.push_back(make_pair(p, cnt));
}
} else {
for (int i=0; i<pcnt && 1LL*prime[i]*prime[i]<=n; ++i) {
if (n % prime[i] == 0) {
int cnt = 0;
for (; n%prime[i]==0; n/=prime[i], ++cnt);
res.push_back(make_pair(prime[i], cnt));
}
}
if (n > 1)
res.push_back(make_pair(n, 1));
}
return res;
}
vector<int> disect(int n) {
vector<int> res;
for (int i=1; 1LL*i*i<=n; ++i) {
if (n % i == 0) {
res.push_back(i);
int ano = n / i;
if (ano != i)
res.push_back(ano);
}
}
sort(res.begin(), res.end());
res.resize(unique(res.begin(), res.end()) - res.begin());
return res;
}
LL bin(LL a, LL b, LL p) {
LL res = 1;
for (; b; b>>=1, a=a*a%p)
if (b & 1) res = res * a % p;
return res;
}
int findsmallest(int n) {
vector<int> v = disect(n);
// dbg(v.size(), n);
for (int x:v) {
// dbg(x);
if (bin(10, x, p) == 1) {
return x;
}
}
return -1;
}
int check1(int p) {
for (int i=1; i<=p; ++i) {
if (bin(10, i, p) ==1) return i;
}
return p;
}
namespace stage2 {
int n, m, p, lim, mlim;
LL ans, dat2[1<<10];
vector<pii> pinfo;
set<int> S;
Frac dat[1<<21];
int solve(LL cur) {
LL res = 0;
for (int i=1; i<mlim; ++i) {
// if (dat[i].a > 0)
// res += cur/dat[i].b;
// else res -= cur/dat[i].b;
res += cur / dat2[i];
}
res = cur - res;
return res;
}
void dfs(int now, LL cur, int minj, bool flag) {
// dbg(now, cur, minj, flag);
if (now == lim) {
if (!flag) {
dbg(solve(n / cur), m-minj+1);
ans += solve(n / cur) * (m - minj + 1);
}
return;
}
const pii &info = pinfo[now];
int p = info.first, jlim = info.second;
cur *= p;
for (int i=1; cur<=n; cur*=p, ++i) {
int newminj = minj;
// if (i < jlim) {
newminj = max(newminj, (jlim + (i-1))/ i);
// }
dfs(now+1, cur, newminj, flag && (i >= jlim));
}
}
LL solve(int _n, int _m, int _p) {
S.clear();
n = _n;
m = _m;
p = _p;
ans = 0;
pinfo = primed(p);
for (const pii &p:pinfo)
S.insert(p.first);
lim = pinfo.size();
mlim = (1<<lim);
dat[0] = Frac(0, 1);
for (int mask = 1; mask < mlim; ++ mask) {
int bitcnt = 0, cb = 1;
for (int j=0; j<lim; ++j) {
if ((mask >> j) & 1) {
++bitcnt;
cb *= pinfo[j].first;
}
}
if (bitcnt % 2 == 0) cb = -cb;
dat[mask] = Frac(1, cb);
dat2[mask] = cb;
}
dfs(0, 1, 1, true);
dbg(ans);
ans += (n / p) * m;
return ans;
}
int check() {
int ans = 0;
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j) {
if (bin(i, j, p) == 0) {
// dbg(i);
++ans;
}
}
return ans;
}
}
LL calc(int n, int m, int p) {
return stage2::solve(n, m, p);
}
int ccheck() {
LL ans = 0;
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j) {
LL x = bin(i, j, p-1);
x = bin(10, x, p);
if (x == 1) ++ans;
}
return ans;
}
void solve() {
if (p == 2 || p == 5) {
puts("0");
return;
}
int x = -1;
if (p == 3) {
x = 3;
} else {
// stage 1
x = findsmallest(p-1);
}
// int ax = check1(p);
// dbg(x, ax);
dbg(x);
LL ans = calc(n, m, x);
printf("%lld
", ans);
}
signed main(int argc, char const *argv[])
{
// Frac a(2, 5), b(3, 6);
// a = a + b;
// printf("%lld %lld
", a.a, a.b);
// return 0;
// freopen("out.txt", "w", stdout);
init();
int t;
scanf("%lld", &t);
for (int kk=0; kk<t; ++kk) {
scanf("%lld%lld%lld", &p, &n, &m);
solve();
}
return 0;
}
Problem F
题意：求最大的子矩阵，保证子矩阵中的任意两个元素的差 le m 。
题解：考虑枚举上下行边界，把每一列的 max 信息和 min 信息压在一起，然后题目就变成了找一个最长的子区间，使得 max - min le m 。
这个可以用单调队列优化， max 信息维护单调递减数列， min 信息维护单调递增数列，每次从队尾加入元素，将超过 m 的信息从队头移出。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline char nc(){
// /*
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
//*/return getchar();
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(char &x){
for (x=nc();!(x=='('||x==')');x=nc());
}
inline int read(char *s)
{
char c=nc();int len=1;
for(;!(c=='('||c==')');c=nc()) if (c==EOF) return 0;
for(;(c=='('||c==')');s[len++]=c,c=nc());
s[len++]=' ';
return len-2;
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int T,n,m,a[510][510],Max[510],Min[510];
struct Q{
int l,r,q[510];
void init(){l=1;r=0;}
int front(){return q[l];}
int back(){return q[r];}
void push(int x){q[++r]=x;}
void pop(){l++;}
void popback(){r--;}
}qmax,qmin;
int main()
{
read(T);
while(T--)
{
read(n);read(m);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
read(a[i][j]);
int ans=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
Max[j]=a[i][j],Min[j]=a[i][j];
for (int j=i;j<=n;j++)
{
qmax.init();qmin.init();int l=1;
for (int k=1;k<=n;k++)
{
while(qmax.r>=qmax.l&&Max[qmax.back()]<=Max[k]) qmax.popback();
qmax.push(k);
while(qmin.r>=qmin.l&&Min[qmin.back()]>=Min[k]) qmin.popback();
qmin.push(k);
while(qmax.r>=qmax.l&&qmin.r>=qmin.l&&Max[qmax.front()]-Min[qmin.front()]>m)
{
l++;
while(qmax.r>=qmax.l&&qmax.front()<l) qmax.pop();
while(qmin.r>=qmin.l&&qmin.front()<l) qmin.pop();
}
//cout<<i<<" "<<j<<" "<<l<<" "<<k<<endl;
ans=max(ans,(j-i+1)*(k-l+1));
}
for (int k=1;k<=n;k++)
Max[k]=max(Max[k],a[j+1][k]),Min[k]=min(Min[k],a[j+1][k]);
//cout<<Max[k]<<","<<Min[k]<<endl;
}
}
printf("%d
",ans);
}
return 0;
}
/*
1
4 6
5 1 4 4
9 10 8 7
7 9 9 8
3 8 5 7
*/
Problem G
题意：定义一个取石子游戏的游玩过程：单人游戏，若石子总和为奇数，最少的一个石子堆拿走一个。若为偶数，可挑选两个非空石子堆各取走一个。如果不能取了石子还没取完就输了。给定一些石子堆，求有多少个二元组 (l,r) 使得区间的石子堆是能赢的。
题解：首先有个结论：最多的石子小于等于剩下石子总和时，是能赢的。考虑统计不可行的区间：然后枚举每个最大值，向左枚举左端点，向右扩展直到求出最大的不可行区间。比不可行区间少的区间肯定更不可行。看似是个 O(n^2)
的暴力，实际上输出统计的情况，竟然发现是 O(n) 的，实际上也比 O(nlogn)
的不知道快到哪里去了。感性来讲不可行的区间是少的也是短的，严谨的并不会证明。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define zerol
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << " 33[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << " 33[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
//--------------------------------------------------------------------------------------------
const int SP = 20, MAXN = 3e5+5;
typedef pair<int, int> pii;
struct ST {
int dat[SP][MAXN], pos[SP][MAXN];
int Log[MAXN], p2[SP];
void precalc() {
p2[0] = 1;
for (int i=1; i<SP; ++i)
p2[i] = p2[i-1] << 1;
Log[1] = 0;
for (int i=2; i<MAXN; ++i)
Log[i] = Log[i>>1] + 1;
}
void init(int a[], int n) {
for (int i=0; i<SP; ++i) {
memset(dat[i], 0, sizeof(int) * (n+1));
memset(pos[i], 0, sizeof(int) * (n+1));
}
for (int i=1; i<=n; ++i) {
pos[0][i] = i;
dat[0][i] = a[i];
}
for (int i=1; i<SP; ++i)
for (int j=1; j<=n; ++j) {
dat[i][j] = dat[i-1][j];
pos[i][j] = pos[i-1][j];
int rpos = min(n, j+p2[i-1]);
if (dat[i-1][rpos] > dat[i][j]) {
dat[i][j] = dat[i-1][rpos];
pos[i][j] = pos[i-1][rpos];
}
}
}
pii q(int L, int R) {
int lg = Log[R-L+1];
if (dat[lg][L] >= dat[lg][R-p2[lg]+1])
return make_pair(dat[lg][L], pos[lg][L]);
else
return make_pair(dat[lg][R-p2[lg]+1], pos[lg][R-p2[lg]+1]);
}
} st;
int n, a[MAXN];
LL sum[MAXN];
typedef long long ll;
int bs1(int l,int r,ll v, LL s[]){
int m;
if (s[r]<v) return r+1;
while (l<r-1){
m=(l+r)>>1;
if (s[m]>=v) r=m;else l=m+1;
}
return (s[l]>=v)?l:r;
}
int bs2(int l,int r,ll v, LL s[]){
int m;
if (s[l-1]>v) return l-1;
while (l<r-1){
m=(l+r)>>1;
if (s[m-1]<=v) l=m;else r=m-1;
}
return (s[r-1]<=v)?r:l;
}
bool check(int l, int r, LL amax) {
LL s = sum[r] - sum[l-1], t = s - amax * 2;
dbg(s, t, l, r, amax);
if (s % 2) --t;
return t >= 0;
}
LL dfs(int l, int r) {
if (l >= r) return 0;
pii p = st.q(l, r);
int mid = p.second;
// dbg(l, mid, r);
LL ans = 0;
if (mid-l <= r-mid) {
for (int i=l; i<=mid; ++i) {
LL tar = 2LL * p.first + sum[i-1];
// dbg(tar, lower_bound(sum+l, sum+r+1, tar) - sum);
int pos = lower_bound(sum+mid, sum+r+1, tar) - sum;
// while (sum[pos] < tar && pos <= r) ++pos;
if (pos != bs1(mid, r, tar, sum)) {
dbg(pos, sum[pos], tar);
exit(0);
}
ans += r - pos + 1;
}
} else {
for (int i=r; i>=mid; --i) {
LL tar = - 2LL * p.first + sum[i];
int pos = upper_bound(sum+l-1, sum+mid, tar) - sum;
// while (sum[pos] <= tar && pos >= l) --pos;
if (pos != bs2(l, mid, tar, sum)) {
dbg(pos, l, mid, sum[pos], tar, bs2(l, mid, tar, sum));
exit(0);
}
ans += pos-l+1;
// dbg(tar, pos, p.first, l, r, mid, ans);
}
}
ans += dfs(l, mid-1);
ans += dfs(mid+1, r);
return ans;
}
struct ios {
inline char read(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char c11,boo;
for(c11=read(),boo=0;!isdigit(c11);c11=read()){
if(c11==-1)return *this;
boo|=c11=='-';
}
for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
boo&&(x=-x);
return *this;
}
} io;
int main(int argc, char const *argv[])
{
st.precalc();
int t;
io >> t;
for (int kk=0; kk<t; ++kk) {
io >> n;
for (int i=1; i<=n; ++i) {
io >> a[i];
sum[i] = sum[i-1] + a[i];
}
st.init(a, n);
printf("%lld
", dfs(1, n));
}
return 0;
}
Problem H
题意：给出 2k 个坐标在 [-1000,1000] 的整点，求一条直线，使其不经过给定的点，且左右两侧有相同数量的点。
题解：按 x-y 的顺序对点的坐标排序，在第 k 个点的上方 frac{1}{2} 单位距离划一条微微向右下倾斜的直线即可。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << " 33[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << " 33[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
inline char nc(){
/*
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
*/return getchar();
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(char &x){
for (x=nc();!(x=='('||x==')');x=nc());
}
inline int read(char *s)
{
char c=nc();int len=1;
for(;!(c=='('||c==')');c=nc()) if (c==EOF) return 0;
for(;(c=='('||c==')');s[len++]=c,c=nc());
s[len++]=' ';
return len-2;
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
struct node{
int x,y;
node(int x=0,int y=0):x(x),y(y){}
};
bool operator < (node a,node b){
if (a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
const int maxn=1e3+5,inf=1e6+5;
node a[maxn];
int main(){
int tt;
int i,n;
scanf("%d",&tt);
while (tt--){
scanf("%d",&n);
for (i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+n);
printf("%d %d %d %d
",a[n/2].x-1,a[n/2].y+inf,a[n/2].x+1,a[n/2].y-inf-1);
}
return 0;
}
Problem I
题意：一个新数列是通过原来数列的每三个数产生一个中位数得到的，给出新数列，求一个任意的原数列。
题解：一个结论是，如果有解，那么一定可以让每个位置最终的值，是它所能影响到的 3 个中位数之一。
于是我们可以处理出每个数影响到的三个数，然后 f[i][j][k] 表示位置为 i-1 的数取他影响的 j 个数，位置为 i 的数取他影响的 k 个数的方案是否存在。dp 转移的时候记录前置转移状态，最后 dfs 一下输出一个可行解就行了。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int T,n,m,g[100010][3],a[100010];
struct data
{
int x,y,z,flag;
data(int a=0,int b=0,int c=0,int d=0):x(a),y(b),z(c),flag(d){}
}f[100010][3][3];
void solve(int x,int y,int z)
{
if (x==0) {printf("%d ",a[1]);return ;}
solve(f[x][y][z].x,f[x][y][z].y,f[x][y][z].z);
printf("%d ",g[x][z]);
}
bool check(int x,int y,int z,int a)
{
if (x>y) swap(x,y);
if (x>z) swap(x,z);
if (y>z) swap(y,z);
if (y!=a) return false;
return true;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for (int i=1;i<=n-2;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
{
int s=0;
for (int j=max(1,i-2);j<=min(i,n-2);j++)
g[i][s++]=a[j];
//printf("i=%d %d %d %d
",i,g[i][0],g[i][1],g[i][2]);
}
for (int i=1;i<=n;i++)
for (int j=0;j<3;j++)
for (int k=0;k<3;k++)
f[i][j][k].flag=0;
f[2][0][0]=data(0,0,0,1);
if (n>3) f[2][0][1]=data(0,0,0,1);
for (int i=2;i<n;i++)
for (int j=0;j<3;j++)
for (int k=0;k<3;k++)
if (f[i][j][k].flag)
{
for (int l=0;l<3;l++)
if (check(g[i-1][j],g[i][k],g[i+1][l],a[i-1]))
f[i+1][k][l]=data(i,j,k,1);
//printf("%d %d from %d %d
",i+1,g[i+1][l],g[i-1][j],g[i][k]);
}
int flag=0;
for (int j=0;j<2;j++)
if (f[n][j][0].flag)
{
solve(f[n][j][0].x,f[n][j][0].y,f[n][j][0].z);
printf("%d
",g[n][0]);
flag=1;
break;
}
if (!flag) puts("-1");
}
return 0;
}
Problem J
题意：模拟 LRU
题解：用时间标记维护一个 set，再用一个 map 记录名字到时间标记的映射。这样既可以通过时间标记访问，又可以通过名字访问。复杂度 O(nlogn) ，听说卡常很厉害
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
// #define zerol
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(char &x){
for (x=nc();!(x=='('||x==')');x=nc());
}
inline int read(char *s)
{
char c=nc();int len=1;
for(;!(isdigit(c));c=nc()) if (c==EOF) return 0;
for(;(isdigit(c));s[len++]=c,c=nc());
s[len++]=' ';
return len-2;
}
int wt,ss[19];
struct node {
int tag;
LL name;
int data;
node(){}
node(int tag=0, LL name=0, int data=0):tag(tag), name(name), data(data){}
bool operator < (const node &other) const {
if (tag != other.tag)
return tag < other.tag;
else if (name != other.name)
return name < other.name;
else
return data < other.data;
}
};
set<node> S;
map<LL, int> mp;
int n, q;
int main() {
int t;
read(t);
for (int kase=0; kase<t; ++kase) {
S.clear();
mp.clear();
read(q);
read(n);
dbg(q, n);
LL name;
int data, opt;
char sname[20];
for (int kk=0; kk<q; ++kk) {
int tag = kk;
read(opt);
int slen = read(sname);
read(data);
dbg(opt, slen, data);
name = 1;
for (int i=1; i<=slen; ++i) {
name = name * 10 + sname[i] - '0';
}
if (opt == 0) {
int tmptag, result;
if (mp.count(name)) {
tmptag = mp[name];
node now(tmptag, name, -100);
set<node>::iterator it = S.lower_bound(now);
node newn(kk, name, it->data);
result = it->data;
S.erase(it);
S.insert(newn);
mp[name] = kk;
} else {
S.insert(node(kk, name, data));
result = data;
}
mp[name] = kk;
printf("%d
", result);
} else {
bool suc = true;
if (!mp.count(name)) {
suc = false;
} else {
node now(mp[name], name, -100);
set<node>::iterator it = S.lower_bound(now);
int res = -1;
if (data == 0) {
if (it == S.end())
suc = false;
else
res = it->data;
} else if (data == 1) {
if (it == S.end())
suc = false;
else {
++it;
if (it == S.end())
suc = false;
else {
res = it->data;
}
}
} else if (data == -1) {
if (it == S.begin() || it == S.end()) {
suc = false;
} else {
--it;
res = it->data;
}
}
if (suc) printf("%d
", res);
}
if (!suc) puts("Invalid");
}
if (S.size() > n) {
LL name = S.begin()->name;
mp.erase(mp.lower_bound(name));
S.erase(S.begin());
}
}
}
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法：眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络？
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final，JSR-299 的框架
- JavaFX 2012：彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight：基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE：用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络：结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击