本场总结:
题目类型:
A.分块
B.签到
C.巨巨才能A的题
D.数论---找最小循环节
E.kruskal重构树--巨巨才能A的题
F.单调队列
G.ST表分治、贪心
H.构造
I:dp
J. unordered_map<string,list<node>::iterator>mp; 模拟</node>
小结:
---点集可以用点异或和，点权可以用随机hash产生.
---数论还得多练
---ST表可以维护最值下标，分治一般取较小侧暴力
---map 存关键字 和 链表索引地址 优雅
A.Graph Games
题意:一个图有n个点m条边关系，有q次操作
(1 l r ):m边关系,翻转 第l条 到 r条边，即存在就删除 或者 不存在就添加.
(2 u v ):询问 S(u) 是否等于 S(v)
S(u) 定义为与点u相连的所有点构成的点集合
分析：将每个点随机hash一个值,点集用异或维护，异或和的值标记为点集.------(常用小技巧)
可以分块写，块维护块标记存翻转次数,块外边关系暴力，具体看实现代码.
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=2e5+10;
const int maxm=500;
int n,m;
int l[maxm],r[maxm],belong[maxn],block,num,q;
int tag[maxm],a[maxn],b[maxn];
ll Hash[maxn],S[maxm][maxn],val[maxn];
void build()
{
block=sqrt(m);
num=m/block;if( m%block ) num++;
for( int i=1;i<=num;i++ ) l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=m;
for( int i=1;i<=m;i++ ) belong[i]=(i-1)/block+1;
for( int i=1;i<=num;i++ )
{
for( int j=1;j<=n;j++ ) S[i][j]=0;
tag[i]=0;
}
for( int i=1;i<=n;i++ ) val[i]=0;
}
void ask( int x,int y )
{
ll sx=val[x],sy=val[y];
for( int i=1;i<=num;i++ )
{
if( !tag[i] )
{
sx^=S[i][x];
sy^=S[i][y];
}
}
putchar( sx==sy ? '1' : '0' );
}
void update( int x,int y )
{
for( int i=x;i<=min(r[belong[x]],y);i++ )
{
val[a[i]]^=Hash[b[i]];
val[b[i]]^=Hash[a[i]];
}
if( belong[x]!=belong[y] )
{
for( int i=l[belong[y]];i<=y;i++ )
{
val[a[i]]^=Hash[b[i]];
val[b[i]]^=Hash[a[i]];
}
}
for( int i=belong[x]+1;i<belong[y];i++ ) tag[i]^=1;
}
int main()
{
int t;
scanf("%d",&t);
srand( unsigned(time(NULL)) );
for( int i=0;i<maxn;i++ ) Hash[i]=rand();
while( t-- )
{
scanf("%d%d",&n,&m);
build();
for( int i=1;i<=m;i++ )
{
scanf("%d%d",&a[i],&b[i]);
S[belong[i]][a[i]]^=Hash[b[i]];
S[belong[i]][b[i]]^=Hash[a[i]];
}
scanf("%d",&q);
while( q-- )
{
int opt,l1,r1;
scanf("%d%d%d",&opt,&l1,&r1);
if( opt==1 ) update(l1,r1);
else ask(l1,r1);
}
putchar('\n');
}
return 0;
}B.Crazy Binary String
题意：求多少子串和子序列满足0和1个数相同
子串满足条件：转化为 0标记为-1,1标记为1 , 求前缀和。l~r的子串满足即为sum[r]-sum[l-1]=0
举个例子 序列 0 0 0 1 1 1，经过前缀和是 -1 -2 -3 -2 -1 0,我们只记录某个前缀第一次出现的位置，和下一次出现的位置，我们就知道，这两个相同前缀之间的串的零一数目是相同的.我们还需要统计前缀和中值为0的长度，即为答案
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int p[maxn<<1];
char s[maxn];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s+1);
memset(p,-1,sizeof(p));
int ans1=0,ans2=0,sum=100000,len=strlen(s+1);
p[sum]=0;
for( int i=1;i<=len;i++ )
{
if( s[i]=='0' )
{
ans2++;
sum--;
}
else sum++;
if( p[sum]==-1 ) p[sum]=i;
else ans1=max(ans1,i-p[sum]);
}
ans2=min(ans2,n-ans2)*2;
printf("%d %d\n",ans1,ans2);
}C.Guessing ETT
规律结论模拟题 过的人太少 留坑没想法
D.Big Integer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll poww( ll a,ll b,ll mod )
{
ll ans=1;
while( b )
{
if( b&1 ) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
ll poww(ll a,ll b )
{
ll ans=1;
while( b )
{
if( b&1 ) ans=ans*a;
b>>=1;
a=a*a;
}
return ans;
}
vector< pair<int,int> > a;
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
a.clear();
ll p,n,m;
scanf("%lld%lld%lld",&p,&n,&m);
if( p==2 || p==5 )
{
puts("0");
continue;
}
if( p==3 )
{
printf("%lld\n",n/3*m);
continue;
}
int minn=p-1;
ll x=minn;
for( int i=2;i*i<=x;i++ ) // 找 d 的循环节
{
if( x%i==0 )
{
if( poww(10,i,p)==1 ) minn=min(minn,i);
if( poww(10,x/i,p)==1 ) minn=min(1ll*minn,x/i);
}
}
int maxn=0;
x=minn;
for( int i=2;i*i<=x;i++ ) // 将 d 进行质因数分解
{
if( x%i==0 )
{
int num=0;
while( x%i==0 )
{
num++;x/=i;
}
maxn=max(maxn,num);
a.push_back( make_pair(i,num) );
if( x==1 ) break;
}
}
if( x>1 )
{
maxn=max(maxn,1);
a.push_back( make_pair(x,1) );
}
ll ans=0;
ll g=1;
for( int j=1;j<=min(1ll*maxn,m);j++ )
{
g=1;
for( int i=0;i<a.size();i++ )
{
ll num=(a[i].second+j-1)/j; //上取整
g=g*poww(a[i].first,num);
}
ans=ans+n/g; // 1~n 中有n/g个合法的 i
}
if( m>maxn )
{
ans=ans+n/g*(m-maxn); // m的值大于最大的指数 直接计算即可
}
printf("%lld\n",ans);
}
return 0;
}E.Trees in the Pocket II
什么kruskal重构树 个位数过题 留坑没想法
F.Planting Trees
题意：一个二维平面内的每个点都有个树，树有高度。
然后让你找一个最大区域，满足区域內任意两树的高度差.
思路：枚举了左边界之后，用两个单调队列去维护区间内的最大值和最小值
然后就算区间最大和最小的差值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=5e2+10;
int t,n,m,ans;
int que1[N], que2[N];//单调队列
int minn[N], maxx[N], h[N][N];
int main()
{
scanf("%d",&t);
while( t-- )
{
scanf("%d%d",&n,&m);
ans=0;
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=n;j++ ) scanf("%d",&h[i][j]);
}
for( int i=1;i<=n;i++ ) // 上边界
{
memset(maxx,0,sizeof(maxx));
memset(minn,inf,sizeof(minn));
for( int j=i;j<=n;j++ ) //下边界
{
for( int k=1;k<=n;k++ ) // 右边界
{
minn[k]=min(minn[k],h[j][k]); // 前缀最小值
maxx[k]=max(maxx[k],h[j][k]); // 前缀最大值
}
int l1=1,r1=0,l2=1,r2=0;
int l=1; // 初始化左边界
for( int k=1;k<=n;k++ ) // 右边界
{
while( l1<=r1 && maxx[k]>=maxx[ que1[r1] ] ) //维护队列单调递减
{
r1--;
}
que1[++r1]=k;
while( l2<=r2 && minn[k]<=minn[ que2[r2] ] ) //维护队列单调递增
{
r2--;
}
que2[++r2]=k;
while( l1<=r1 && l2<=r2 && maxx[ que1[l1] ]-minn[ que2[l2] ]>m )
{
l = min(que1[l1]+1, que2[l2]+1); // 寻找符合条件的最近左边界
while (l1<=r1 && que1[l1]<l) l1++; //将不符合条件的左边界出队
while (l2<=r2 && que2[l2]<l) l2++; //将不符合条件的左边界出队
}
ans=max( ans,(j-i+1)*(k-l+1) );
}
}
}
printf("%d\n",ans);
}
}G.Removing Stones
此题有两种方法:ST表加分治O(nlogn*logn)，贪心O(n)
方法一：ST表有个小技巧，维护最大值的下标
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=3e5+10;
const int maxm=30;
int n,k;
int d[maxn][maxm]; //---> 最大值
int a[maxn];
ll sum[maxn];
// 原题目等价于: 求有多少个长度不小于2的连续数列，
// 使得其中最大元素不大于所有元素和的1/2
// 2*maxx<=sum[r]-sum[l-1] ---> 2*maxx+sum[l-1]<=sum[r]
// ---> sum[r]-2*maxx>=sum[l-1]
int max( int i,int j ) // 重写max st表维护的是下标
{
if(a[i]>=a[j]) return i;
else return j;
}
void st()
{
int m,i,j;
for( int i=1;i<=n;i++ ) d[i][0]=i; // 维护下标对应值最大
m=log2(n);
for( j=1;j<=m;j++ )
{
for( i=1;i+(1<<j)-1<=n;i++ )
{
d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
}
}
int RMQ_max( int l,int r )
{
int m=(int)(log(r-l+1.0)/log(2.0));
return max( d[l][m],d[r-(1<<m)+1][m] );
}
ll ans=0;
void solve( int l,int r )
{
if( l>=r ) return;
int mid=(l+r)>>1;
int x=RMQ_max(l,r);
if( x<=mid ) // 分治选取 较小侧 才能降至 log
{
for( int i=l;i<=x;i++ )
{
int pos=lower_bound( sum+x,sum+r+1,sum[i-1]+2*a[x] )-sum;
ans+=(r-pos+1);
}
}
else
{
for( int i=x;i<=r;i++ )
{
int pos=upper_bound(sum+l-1,sum+x,sum[i]-2*a[x])-sum; //
ans+=(pos-l+1);
}
}
solve(l,x-1);
solve(x+1,r);
}
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
scanf("%d",&n);
ans=0;
for( int i=1;i<=n;i++ )scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
st();
solve(1,n);
printf("%lld\n",ans);
}
}方法二:就是我们对于每个数都看把这个数当成最大值得左边界和右边界的和，然后求是否这个区间成立。
但是这里不好统计有多少成立的区间，于是便反向取，即求有多少不满足的区间。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
int n,m;
ll a[maxn];
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
scanf("%d",&n);
ll ans=1ll*n*(n+1)/2;
for( int i=1;i<=n;i++ ) scanf("%lld",&a[i]);
for( int i=1;i<=n;i++ )
{
ll sum=0,l=i,r=i;
while( l>1 && a[i]>sum+a[l-1] )
{
l--;
sum+=a[l];
}
while( l<=i )
{
while( r<n && a[i]>sum+a[r+1] )
{
r++;
sum+=a[r];
}
ans-=(r-i+1);
sum-=a[l];
l++;
}
}
printf("%lld\n",ans);
}
}H. Magic Line
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int M=5e8+5;
vector< pair<int,int> > p;
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
int n;
scanf("%d",&n);
p.clear();
for( int i=1;i<=n;i++ )
{
int x,y;
scanf("%d%d",&x,&y);
p.push_back( make_pair(x,y) );
}
sort(p.begin(),p.end());
int mid=(n+1)/2;
pair<int,int> q=p[mid];
int x1=q.first-1,x2=q.first+1,y1=M-1,y2=2*q.second-M;
printf("%d %d %d %d\n",x1,y1,x2,y2);
}
}I.Median
dp题，难点就是推构造结论
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int t,n;
int ans[maxn]; // 答案序列
int b[maxn]; // 中位数序列
int can[maxn][4]; // 第i个位置 可构造选择数字
int dp[maxn][4][4]; //
int pre[maxn][4][4]; // 每个状态 回溯索引
int mid( int a,int b,int c ) // 找中位数
{
if( a>b ) swap(a,b);
if( b>c ) swap(b,c);
if( a>b ) swap(a,b);
return b;
}
int main()
{
scanf("%d",&t);
while( t-- )
{
scanf("%d",&n);
for( int i=3;i<=n;i++ ) scanf("%d",&b[i]); // 下标从 3 开始 为第一个中位数 即 b[i] 影响 a[i-2] a[i-1] a[i]
b[1]=b[2]=b[3]; //填充a1 与中位数 b[1] b[2] b[3] 相关
b[n+2]=b[n+1]=b[n];// an 与 中位数 b[n] b[n+1] b[n+2] 相关
for( int i=1;i<=n;i++ ) // can数组维护 a[i] 可填的中位数b[i]
{
can[i][1]=b[i];
can[i][2]=b[i+1];
can[i][3]=b[i+2];
// sort(can[i]+1,can[i]+3);
}
for( int i=1;i<=n;i++ ) // 初始化
{
for( int j=1;j<=3;j++ )
{
for( int k=1;k<=3;k++ )
{
pre[i][j][k]=dp[i][j][k]=0;
}
}
}
for( int i=1;i<=3;i++ ) // 初始化 假如 n==1 即一个中位数 那么直接构造三个数 都是中位数
{
for( int j=1;j<=3;j++ )
{
dp[2][i][j]=1;
}
}
for( int i=3;i<=n;i++ ) // 遍历每一位
{
for( int j=1;j<=3;j++ ) // 遍历 第i-1位 填的数字
{
for( int k=1;k<=3;k++ ) // 遍历 第i位 填的数字
{
for( int l=1;l<=3;l++ )
{
if( dp[i-1][k][l] && mid(can[i-2][l],can[i-1][k],can[i][j])==b[i] ) // 状态转移 b[i] 满足 当前构造的 a[i-2]、a[i-1]、a[i] 的中位数
{
dp[i][j][k]=1;
pre[i][j][k]=l;
}
}
}
}
}
int now,last;
bool isfind=false;
for( int i=1;i<=3;i++ ) //找到可行解
{
for( int j=1;j<=3 && !isfind ;j++ )
{
if( dp[n][i][j] )
{
isfind=true;
now=i;
last=j;
}
}
}
if( !isfind )
{
puts("-1");
continue;
}
for( int i=n;i>=2;i-- ) //回溯
{
ans[i]=can[i][now];
int temp=pre[i][now][last];
now=last;
last=temp;
}
ans[1]=can[1][1];
for( int i=1;i<=n;i++ )
{
printf("%d ",ans[i]);
}
puts("");
}
}J.LRU management
模拟题。学一手map存关键字和链表节点地址
#include<bits/stdc++.h>
using namespace std;
struct node{
int v;
string s;
node(){}
node ( string s,int v ) : s(s),v(v){}
};
list<node> ls;
unordered_map<string,list<node>::iterator>mp;
void read( int &x )
{
int f=1;x=0;char s=getchar();
for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
for( ;isdigit(s);x=x*10+s-48,s=getchar());
x*=f;
}
int main()
{
int n,m,t;
scanf("%d",&t);
while( t-- )
{
ls.clear();mp.clear();
read(n);read(m);
int opt,v;
char s[20];
for( int i=0;i<n;i++ )
{
read(opt);
scanf("%s",s);
read(v);
if( opt==0 )
{
if( mp.find(s)!=mp.end() )
{
auto sw=mp[s];
v=sw->v;
ls.erase(sw);
}
printf("%d\n",v);
node a(s,v);
ls.push_back(a);
mp[s]=prev( ls.end() );
if( ls.size()>m )
{
auto sw=ls.begin();
mp.erase(sw->s);
ls.pop_front();
}
}
else
{
if( mp.find(s)==mp.end() ) puts("Invalid");
else
{
auto sw=mp[s];
if( ( v==1 && next(sw)==ls.end() ) || ( v==-1 && sw==ls.begin() ) ) puts("Invalid");
else
{
if( v==1 ) sw=next(sw);
else if( v==-1 ) sw=prev(sw);
printf("%d\n",sw->v);
}
}
}
}
}
} 
京公网安备 11010502036488号