A. Equivalent Prefixes
--两个单调栈维护
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int a[maxn],b[maxn];
int dp1[maxn],dp2[maxn];
int main()
{
int n;
while( ~scanf("%d",&n) )
{
for( int i=1;i<=n;i++ ) scanf("%d",&a[i]);
for( int i=1;i<=n;i++ ) scanf("%d",&b[i]);
stack<int>p,q;
int ans=1;
for( int i=1;i<=n;i++ )
{
if( p.empty() )
{
dp1[i]=i;
p.push(i);
}
else
{
while( !p.empty() && a[p.top()]>a[i] ) p.pop();
if(!p.empty() ) dp1[i]=p.top();
else dp1[i]=i;
p.push(i);
}
if( q.empty() )
{
dp2[i]=i;
q.push(i);
}
else
{
while( !q.empty() && b[q.top()]>b[i] ) q.pop();
if(!q.empty() ) dp2[i]=q.top();
else dp2[i]=i;
q.push(i);
}
if( dp1[i]==dp2[i] ) ans=i;
else break;
}
printf("%d\n",ans);
}
}E. ABBA
待补
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+5;
const int mod=1e9+7;
ll dp[maxn][maxn];
int main()
{
int n,m;
while( ~scanf("%d%d",&n,&m) )
{
for( int i=0;i<=n+m;i++ )
{
for( int j=0;j<=n+m;j++ ) dp[i][j]=0;
}
dp[0][0]=1;
for( int i=0;i<=n+m;i++ )
{
for( int j=0;j<=n+m;j++ )
{
if( i-j<=n && i>0 ) dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
if( j-i<=m && j>0 ) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
}
}
printf("%lld\n",dp[n+m][n+m]);
}
}
F. Random Point in Triangle
手推结论或者随机数找规律 (待补找规律过程)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll a,b,c,d,e,f;
while( ~scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&f) )
{
printf("%lld\n",1ll*abs(a*d+c*f+e*b-c*b-e*d-a*f)*11);
}
return 0;
}
H. XOR
很明显是一题线性基的题目
题意:给定n个整数，求满足子集异或和为0的子集大小之和。
题解：相当于求每个数出现在子集中的次数之和。
先对n个数求线性基，设线性基大小为r，可以分别计算线性基内数的贡献和线性基外数的贡献
1.线性基外：共n-r个数，枚举每个数x，将线性基外剩余的n-r-1个数任意排列，显然共有
2.线性基内：枚举每个数x，将所有剩余的n-1个数再求一次线性基，设为B，分两种情况：
(1).x不能被B异或出。那么显然x不能在任意一个集合中出现，x的贡献为0。
(2).x可以被B异或出。此时B的大小必定也为r，因为B已经能表示所有n个数了。那么在除去x和B的情况下，剩余n-r-1个数显然也是任意排列，x贡献为
#include<bits/stdc++.h>
using namespace std;
// 求每个数出现在子集的次数之和
// 先对n个数求线性基，设线性基大小为 r，可以分别计算线性基内数的贡献和线性基外数的贡献
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
int n,k;
struct Linear_Basis
{
static const int wei=63;
ll p[wei],np[wei],r;
void init()
{
r=0;
memset(p,0,sizeof(p));
memset(np,0,sizeof(np));
}
bool ins( ll x )
{
for( int i=wei-1;i>=0;i-- )
{
if( x>>i & 1 )
{
if( p[i] ) x^=p[i];
else
{
++r;
p[i]=x;
break;
}
if( !x ) break;
}
}
return x>0 ; // 线性无关 or 线性相关
}
}LB,L;
ll a;
vector<ll> vec;
ll qpow( ll x,ll y )
{
ll ans=1;
while( y )
{
if( y&1 ) ans=ans*x%mod;
y>>=1;
x=x*x%mod;
}
return ans;
}
int main()
{
while( ~scanf("%d",&n) )
{
LB.init();L.init();
vec.clear();
for( int i=1;i<=n;i++ )
{
scanf("%lld",&a);
if( LB.ins(a) ) vec.push_back(a);
else L.ins(a);
}
ll ans=qpow(2,n-LB.r-1)*(n-LB.r)%mod; // 线性基外
for( int i=0;i<vec.size();i++ )
{
Linear_Basis tp(L);
for( int j=0;j<vec.size();j++ )
{
if( i!=j ) tp.ins(vec[j]);
}
if( tp.r==LB.r ) ans=(ans+qpow(2,n-LB.r-1))%mod;
// n个数生成的不同线性基个数相等，所以只需判断线性基个数是否相同，
// 就可以判断a[i]是否能放进去
}
printf("%lld\n",ans);
}
}
I. Points Division
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
struct node{
int x,y,a,b;
}p[maxn];
int n,m,num[maxn],tot;
struct ST
{
#define ls i << 1
#define rs i << 1 | 1
struct node
{
ll max, lazy;
int l, r;
}
T[maxn<< 2];
inline void push_up(int i)
{
T[i].max = max(T[ls].max, T[rs].max);
}
void build(int i, int l, int r)
{
T[i] = node{0, 0, l, r};
if (l == r)
{
T[i].max = -inf;
T[i].lazy = 0;
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(i);
}
inline void push_down(int i)
{
T[ls].lazy += T[i].lazy;
T[rs].lazy += T[i].lazy;
T[ls].max += T[i].lazy;
T[rs].max += T[i].lazy;
T[i].lazy = 0;
}
void update(int i, int l, int r, ll x)
{
if (l > r)
return;
if ((T[i].l == l) && (T[i].r == r))
{
T[i].lazy += x;
T[i].max += x;
return;
}
if (T[i].lazy != 0)
push_down(i);
int mid = (T[i].l + T[i].r) >> 1;
if (mid >= r)
update(ls, l, r, x);
else if (mid < l)
update(rs, l, r, x);
else
{
update(ls, l, mid, x);
update(rs, mid + 1, r, x);
}
push_up(i);
}
void upd(int i, int pos, ll x)
{
if (T[i].l == T[i].r)
{
T[i].max = max(T[i].max, x);
return;
}
if (T[i].lazy != 0)
push_down(i);
int mid = (T[i].l + T[i].r) >> 1;
if (mid >= pos)
upd(ls, pos, x);
else
upd(rs, pos, x);
push_up(i);
}
ll getmax(int i, int l, int r)
{
if (l > r)
return 0;
if ((T[i].l == l) && (T[i].r == r))
return T[i].max;
if (T[i].lazy != 0)
push_down(i);
int mid = (T[i].l + T[i].r) >> 1;
if (mid >= r)
return getmax(ls, l, r);
else if (mid < l)
return getmax(rs, l, r);
else
return max(getmax(ls, l, mid), getmax(rs, mid + 1, r));
}
} seg;
inline bool cmp(node a, node b)
{
return a.x == b.x ? a.y > b.y : a.x < b.x;
}
int main()
{
while( ~scanf("%d",&n) )
{
tot=0;
for( int i=1;i<=n;i++ )
{
scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].a,&p[i].b);
num[++tot]=p[i].y;
}
sort(num+1,num+1+tot);
tot=unique(num+1,num+1+tot)-num-1;
for( int i=1;i<=n;i++ )
{
p[i].y=lower_bound(num+1,num+1+tot,p[i].y)-num+1;
}
tot++;
sort(p+1,p+1+n,cmp);
seg.build(1,1,tot);
seg.upd(1,1,0);
for( int i=1;i<=n;i++ )
{
ll cur=seg.getmax(1,1,p[i].y);
seg.upd(1,p[i].y,cur+p[i].b); //单点更新
seg.update(1, p[i].y + 1, tot, p[i].b); // 区间更新
seg.update(1, 1, p[i].y - 1, p[i].a);
}
printf("%lld\n", seg.T[1].max);
}
return 0;
}J.Fraction Comparision
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll x,a,y,b;
while( ~scanf("%lld %lld %lld %lld",&x,&a,&y,&b) )
{
if( x*b==y*a )puts("=");
else puts( x/a==y/b?( ( (x%a)*b>(y%b)*a )?">":"<") : (x/a>y/b?">":"<") );
}
}
京公网安备 11010502036488号