T1
很有意思的贪心。
显然只有四种情况：\(a\) 为 \(1/2\)，\(b\) 为 \(1/2\)。
那么为这四种情况分别记录一个 \(vector\)。
我们记录 \(suma\) 为 \(a\) 的总和，\(sumb\) 为 \(b\) 的总和。
那么显然我们需要让这个分配方式达到 \(suma/2\) 和 \(sumb/2\)。
考虑贪心，先将两个都卡在同一起跑线上，然后用 \(11\) 或者 \(22\) 或者 \(12+21\) 操作来贪心即可。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , m , a[N] , b[N] , flag , ans[N];
vector<int> cnt11 , cnt12 , cnt21 , cnt22;
signed main ()
{
freopen ( "slauqe.in" , "r" , stdin );
freopen ( "slauqe.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
int flag = 1;
cnt11.clear() , cnt12.clear() , cnt21.clear() , cnt22.clear();
memset ( ans , 0 , sizeof ans );
n = read();
int suma = 0 , sumb = 0;
for ( int i = 1 ; i <= n ; i ++ ) suma += ( a[i] = read() );
for ( int i = 1 ; i <= n ; i ++ ) sumb += ( b[i] = read() );
for ( int i = 1 ; i <= n ; i ++ )
{
if ( a[i] == 1 && b[i] == 2 ) cnt12.eb(i);
if ( a[i] == 2 && b[i] == 1 ) cnt21.eb(i);
if ( a[i] == 1 && b[i] == 1 ) cnt11.eb(i);
if ( a[i] == 2 && b[i] == 2 ) cnt22.eb(i);
}
if ( suma % 2 || sumb % 2 ) { cout << -1 << endl; continue; }
int dec = abs ( suma / 2 - sumb / 2 );
int need = min ( suma , sumb ) / 2;
if ( suma < sumb ) { for ( int i = 1 ; i <= dec ; i ++ ) ans[cnt12.back()] = 1 , cnt12.pb() , -- need; } //需要12
else { for ( int i = 1 ; i <= dec ; i ++ ) ans[cnt21.back()] = 1 , cnt21.pb() , -- need; }//需要21
int lst = need;
while ( need )
{
if ( need <= cnt11.size() ) { for ( int i = 0 ; i < need ; i ++ ) ans[cnt11[i]] = 1; break; }
else if ( need % 2 == 0 && need <= cnt22.size() * 2 ) { for ( int i = 0 ; i < need / 2 ; i ++ ) ans[cnt22[i]] = 1; break; }
else
{
if ( need >= 3 && cnt12.size() && cnt21.size() )
{
ans[cnt12.back()] = 1 , cnt12.pb();
ans[cnt21.back()] = 1 , cnt21.pb();
need -= 3;
}
else if ( cnt11.size() ) ans[cnt11.back()] = 1 , cnt11.pb() , -- need;
else if ( cnt22.size() && need % 2 == 0 ) ans[cnt22.back()] = 1 , cnt22.pb() , need -= 2;
}
if ( need == lst ) { flag = 0 , cout << -1 << endl; break; }
lst = need;
}
if ( !flag ) continue;
for ( int i = 1 ; i <= n ; i ++ ) cout << ans[i] << ' ';
cout << endl;
}
return 0;
}
T2
结论题。
\(5pts\ O(n^3)\) 暴力：枚举子段，判断有几次必须改。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int N = 300 + 5;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , temp[N] , a[N] , ans , tempb[N];
vector<int> lsh;
signed main ()
{
freopen ( "sort.in" , "r" , stdin );
freopen ( "sort.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read();
for ( int i = 1 ; i <= n ; i ++ ) a[i] = read();
for ( int l = 1 ; l <= n ; l ++ )
for ( int r = l + 1 ; r <= n ; r ++ )
{
int cnt = 0 , suma = 0 , sumb = 0;
for ( int i = l ; i <= r ; i ++ ) temp[i] = a[i];
sort ( temp + l , temp + r + 1 );
for ( int i = l ; i <= r ; i ++ )
{
suma += a[i] , sumb += temp[i];
if ( suma != sumb || a[i] != temp[i] ) ++ cnt;
}
ans += cnt;
}
cout << ans << endl;
return 0;
}
\(20pts\ O(n^2logn)\)：
对于一个点，预处理最远的逆序对，记录在数组中，每次二分查找
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int N = 5e3 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , lst[N][N] , a[N] , cnt[N] , ans;
struct Tree
{
struct node { int sum , add; } t[N<<2];
inl void up ( int p ) { t[p].sum = t[ls].sum + t[rs].sum; }
inl void pushdown ( int p , int l , int r , int val ) { t[p].sum = ( r - l + 1 ) * val , t[p].add = val; }
inl void down ( int p , int l , int r ) { if ( t[p].add ) pushdown ( lson , t[p].add ) , pushdown ( rson , t[p].add ) , t[p].add = 0; }
void build ( int p , int l , int r )
{
t[p].sum = t[p].add = 0;
if ( l == r ) return;
build ( lson ) , build ( rson ) , up(p);
}
void upd ( int p , int l , int r , int x , int y , int val )
{
if ( x > y ) return;
if ( x <= l && r <= y ) return pushdown ( p , l , r , val );
down ( p , l , r );
if ( x <= mid ) upd ( lson , x , y , val );
if ( mid + 1 <= y ) upd ( rson , x , y , val );
up(p);
}
int query ( int p , int l , int r , int x , int y )
{
if ( x <= l && r <= y ) return t[p].sum;
down ( p , l , r );
int res = 0;
if ( x <= mid ) res += query ( lson , x , y );
if ( mid + 1 <= y ) res += query ( rson , x , y );
return res;
}
}T;
int solve ( int x , int y )
{
if ( upper_bound ( lst[y] + 1 , lst[y] + cnt[y] + 1 , x , greater<int>() ) - lst[y] - 1 == 0 ) return inf;
int pos = lst[y][upper_bound ( lst[y] + 1 , lst[y] + cnt[y] + 1 , x , greater<int>() ) - lst[y] - 1];
return pos;
}
signed main ()
{
freopen ( "sort.in" , "r" , stdin );
freopen ( "sort.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read();
for ( int i = 1 ; i <= n ; i ++ ) a[i] = read();
for ( int i = 1 ; i <= n ; i ++ )
{
int tot = 0;
for ( int j = i - 1 ; j ; j -- ) if ( a[j] > a[i] ) lst[i][++tot] = j;
cnt[i] = tot;
}
for ( int i = 1 ; i <= n ; i ++ )
{
// memset ( T.t , 0 , sizeof T.t );
T.build ( 1 , 1 , n );
for ( int j = i + 1 ; j <= n ; j ++ )
{
int lstt = solve ( i , j );
// cout << i << ' ' << j << ' ' << lstt << endl;
T.upd ( 1 , 1 , n , lstt , j , 1 );
ans += T.query ( 1 , 1 , n , i , j );
}
}
cout << ans << endl;
return 0;
}
\(50pts O(nlogn)\)：
一个结论：
\(100pts\) 是单调栈，不想补了。
T3
搜罢。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int N = 1e6 + 5;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , T , seed1 , seed2 , mod , lst , ans , buc[N] , res , x[N] , y[N];
vector<int> temp;
void solve ( int lim , int stp )
{
if ( stp == lim + 1 )
{
int ret = 0;
for ( int i = 1 ; i <= lim ; i ++ ) buc[temp[i]] ^= 1;
for ( int i = 1 ; i <= 1e6 ; i ++ ) if ( !buc[i] ) { ret = i; break; }
for ( int i = 1 ; i <= lim ; i ++ ) buc[temp[i]] = 0;
res = max ( res , ret );
return;
}
temp.eb(x[stp]) , solve ( lim , stp + 1 ) , temp.pb();
temp.eb(y[stp]) , solve ( lim , stp + 1 ) , temp.pb();
}
signed main ()
{
freopen ( "mex.in" , "r" , stdin );
freopen ( "mex.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read() , T = read() , seed1 = read() , seed2 = read() , mod = read();
for ( int i = 1 ; i <= n ; i ++ )
{
if ( i <= T ) x[i] = read() , y[i] = read();
else x[i] = ( ans * i ^ seed1 ) % mod + 1 , y[i] = ( ans * i ^ seed2 ) % mod + 1;
res = 0;
temp.eb(0) , solve(i,1) , temp.pb();
ans ^= ( res * i );
}
cout << ans << endl;
return 0;
}
T4
对于 \(\le 100\) 的点可以模拟。
如果再大一点，我们可以开一个 \(sum_{i,j}\) 数组表示 \(1-i\) 之间值为 \(j\) 的个数，那么我们枚举 \(i,j\)，用前缀和统计合法的 \(k\) 的个数即可。
对于第二个 \(sub\)，我们可以只开 \(6\) 的第二维。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int N = 5e4 + 5;
const int maxn = 5e4;
const int mod = 1e9 + 7;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , m , a[N] , lstans;
namespace sub1
{
void main()
{
for ( int i = 1 , l , r ; i <= m ; i ++ )
{
int ll = ( read() + lstans ) % n + 1 , rr = ( read() + lstans ) % n + 1;
l = min ( ll , rr ) , r = max ( ll , rr );
int res = 0;
for ( int j = l ; j <= r ; j ++ )
for ( int k = l ; k <= r ; k ++ )
for ( int p = l ; p <= r ; p ++ )
res += ( a[j] < a[k] && a[j] * a[j] + a[k] * a[k] == a[p] * a[p] );
cout << ( lstans = res ) << endl;
}
}
}
namespace sub2
{
const int M = 1e3 + 5;
int sum[M][N];
void main()
{
for ( int i = 1 ; i <= n ; i ++ ) ++ sum[i][a[i]];
for ( int i = 1 ; i <= n ; i ++ )
for ( int j = 1 ; j <= maxn ; j ++ )
sum[i][j] += sum[i-1][j];
for ( int i = 1 , l , r ; i <= m ; i ++ )
{
int ll = ( read() + lstans ) % n + 1 , rr = ( read() + lstans ) % n + 1;
l = min ( ll , rr ) , r = max ( ll , rr );
int res = 0;
for ( int j = l ; j <= r ; j ++ )
for ( int k = l ; k <= r ; k ++ )
if ( a[j] < a[k] )
{
int summ = a[j] * a[j] + a[k] * a[k];
int temp = sqrt(summ);
if ( temp * temp != summ || temp > maxn ) continue;
res += sum[r][temp] - sum[l-1][temp];
}
cout << ( lstans = res ) << endl;
}
}
}
namespace sub3
{
const int M = 5e4 + 5;
int sum[M][6];
void main()
{
for ( int i = 1 ; i <= n ; i ++ ) ++ sum[i][a[i]];
for ( int i = 1 ; i <= n ; i ++ )
for ( int j = 3 ; j <= 5 ; j ++ )
sum[i][j] += sum[i-1][j];
for ( int i = 1 , l , r ; i <= m ; i ++ )
{
int ll = ( read() + lstans ) % n + 1 , rr = ( read() + lstans ) % n + 1;
l = min ( ll , rr ) , r = max ( ll , rr );
int res = ( sum[r][3] - sum[l-1][3] ) * ( sum[r][4] - sum[l-1][4] ) * ( sum[r][5] - sum[l-1][5] );
cout << ( lstans = res ) << endl;
}
}
}
signed main ()
{
freopen ( "avidity.in" , "r" , stdin );
freopen ( "avidity.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read() , m = read();
for ( int i = 1 ; i <= n ; i ++ ) a[i] = read();
// if ( n <= 100 ) sub1::main();
if ( n <= 1000 ) sub2::main();
else sub3::main();
return 0;
}