寒假营4
D 数论，特判！！
每次可以把一个数减一，零一个数加一，问最终整个序列有多少种可能的gcd。一个数是整个数组的gcd，他首先一定是每个元素的约数，也就是说所有元素的和是这个数的倍数。
我们现在得到了一个判断的必要条件，但它实际上也是一个充分条件，可以通过构造证明：我们可以把一个数减一，零一个数加一，那么我们实际上就可以把sigma(a(i))的值随意分配到n个位置上。那么如果sigma(a(i))是一个数x的倍数，我们可以把一个元素变成x，剩下的元素都变成kx，k>=1。此时整个序列的gcd就是x了。
前面的比赛时都想到了，但是没考虑到元素个数为1的特判，我以为都说gcd了，肯定至少有两个数吧，结果不是，一个数的gcd是1……以后遇到给一个数组的问题，一定要考虑一下长度为1的情况。
using namespace std;
const int N=2e5+10;
signed main(){
int n;
cin>>n;
if(n==1){//特判
cout<<n;
return 0;
}
long long sum=0;
for(int i=1;i<=n;i++){
int t;
cin>>t;
sum+=t;
}
int ans=0;
for(int i=1;i<=sum/n;i++){
if(sum%i==0&&sum/i>=n)ans++;
//每个数都不小于gcd，因此gcd枚举范围不超过平均值
}
cout<<ans;
}
E前缀和贪心
赛时想复杂了，总觉得贪心会有漏的，结果就是个贪心，从左往右选，如果有合法区间就选上，最后选中区间数就是最大了。唯一一个比较巧妙的地方是，怎么判断有没有可以和当前点组成合法区间的左端点，但这实际上也是一种比较典的思路，把所有左端点存起来，然后每读一个端点，用前缀和或者其他区间查询，检查有没有合法左端点。由于合法区间不能重叠，每次配对后，都要把前面存的左端点都删掉。
using namespace std;
const int N=2e5+10;
int pre[N];
set<int>s;
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
int t;
cin>>t;
pre[i]=(pre[i-1]+t)%k;//预处理前缀和模k
}
s.insert(0);
int ans=0;
for(int i=1;i<=n;i++){
if(s.count(pre[i])){//存在合法左端点
s={pre[i]};//清空之前存的左端点
ans++;//配对
}
else{
s.insert(pre[i]);//不存在合法左端点
//把当前端点也加入左端点集合
}
}
cout<<ans;
}
F dp
每个数可以选或不选，选足六个可以计算一个得分，问得分之和最大值？
首先一个显然的转移是dp[i]=max(dp[i],dp[j]+maxscore(j,i))。这样枚举ij就已经n^2(1e6)了，那么求maxscore(j,i)就不能再是O(n)了。注意到我们枚举j时j是连续变化的，那么maxscore(j,i)和maxscore(j+1,i)可能是可以递推的，这样就可以实现常数复杂度计算了。
具体来说，我们可以维护选1-5个数的最大得分是多少，然后每次都用选5个数得最大的分，加上当前枚举的a(j)作为6个数，去更新dp,然后1-4的最大得分，加上a(j)推出2-5得最大得分，a(j)用来更新选一个的最大得分。计算分数得公式里出现了乘法，那么还需要维护最小值，因为负的最小值乘一个负数也可能是最大值。
using namespace std;
const int N=1e3+10;
int a[N],dp[N];
void fix1(set<int>&a){
while(a.size()>1){
a.erase(a.begin());
}
}
void fix2(set<int>&a){
while(a.size()>1){
a.erase(--a.end());
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
set<int>mn1,mn2,mn3,mn4,mn5;
set<int>mx1,mx2,mx3,mx4,mx5;
for(int j=i;j<=n;j++){
for(auto &k:mx5){//更新dp
dp[j]=max(dp[j],dp[i-1]+k-a[j]);
}
for(auto &k:mn5){
dp[j]=max(dp[j],dp[i-1]+k-a[j]);
}
for(auto &k:mn4){//更新5
mn5.insert(k*a[j]);
mx5.insert(k*a[j]);
}
for(auto &k:mx4){
mn5.insert(k*a[j]);
mx5.insert(k*a[j]);
}
for(auto &k:mx3){//更新4
mn4.insert(k-a[j]);
mx4.insert(k-a[j]);
}
for(auto &k:mn3){
mn4.insert(k-a[j]);
mx4.insert(k-a[j]);
}
for(auto &k:mn2){//更新3
mn3.insert(k*a[j]);
mx3.insert(k*a[j]);
}
for(auto &k:mx2){
mn3.insert(k*a[j]);
mx3.insert(k*a[j]);
}
for(auto &k:mx1){//更新2
mn2.insert(k-a[j]);
mx2.insert(k-a[j]);
}
for(auto &k:mn1){
mn2.insert(k-a[j]);
mx2.insert(k-a[j]);
}
mx1.insert(a[j]);//更新1
mn1.insert(a[j]);
fix1(mx1);//利用set得排序，把没用的都删掉，只留下最值
fix1(mx2);
fix1(mx3);
fix1(mx4);
fix1(mx5);
fix2(mn1);
fix2(mn2);
fix2(mn3);
fix2(mn4);
fix2(mn5);
}
}
cout<<*max_element(dp+1,dp+1+n);
}
G 暴力枚举
虽然一看数据就知道能暴力，但是暴力的写法也是很重要的，好的写法可以很快出，丑的写法可能虽然理论上能写，但实际写起来太麻烦导致写不出来。
一种简洁的写法是，枚举三角形顶点，一行行往下判断，直到越界，判断时就看两点之间是否全是星号。
using namespace std;
int n,m;
char a[550][550];
int pre[550][550];
int ans;
void check(int h,int l,int r){
if(h>n||l<1||r>m)return;//越界返回
if(pre[h][r]-pre[h][l-1]==0)ans++;//全是星号合法
if(a[h][l]=='*'&&a[h][r]=='*')check(h+1,l-1,r+1);//看下一行，边往外扩
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
pre[i][j]=pre[i][j-1]+(a[i][j]=='.');//预处理星号个数前缀和
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*')check(i+1,j-1,j+1);//枚举顶点
}
}
cout<<ans;
}
H 树状数组统计合法对数
遍历所有点就已经1e6了，那么计算合法三角形就不能O(n)暴力了，必须logn。这个复杂度能想到的做法就只剩下树状数组维护合法端点数了。
这其实是一种很经典的思想，问有多少合法数对，暴力做法是n^2枚举所有组合，树状数组做法是，每读一个数，在权值树状数组上存起来，并且利用树状数组的区间查询，计算有多少可以和当前数配对的数。每个数都有一个能配对的范围，用这个范围决定查询区间。根据当前枚举位置，也可以把树状数组中那些作用范围到不了当前位置的数删掉。
具体来说，在这道题里我们要统计的点对就是三角形的顶点和底边中点（当然也可以选别的，比如右下角顶点），作用范围就是这个顶点/底边中点，最远可以和多远的点组成三角形，对底边中点来说就是左右两侧底边长度的最小值，对顶点来说就是左右延伸出的斜边长度的最小值。这些我们可以先预处理。
然后枚举每一列的所有点，每读一个星号，就在树状数组上插入这个点，然后统计这个点和已存在的点能组成的合法点对（三角形）数。横坐标每移动一次，就把失效的底边中点删掉。
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+10;
char a[N][N];
int t[N],n,m,l[N][N],r[N][N],ul[N][N],ur[N][N];
int lowbit(int x){
return x&(-x);
}
int sum(int x){
int sum=0;
while(x>=1){
sum+=t[x];
x-=lowbit(x);
}
return sum;
}
void add(int i,int x){
while(i<=n){
t[i]+=x;
i+=lowbit(i);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
l[i][j]=l[i][j-1]+1;//底边中点向左最大长度
ul[i][j]=ul[i+1][j-1]+1;//向左下斜边最大长度
ur[i][j]=ur[i+1][j+1]+1;//右下斜边最大长度
}
else{
l[i][j]=ur[i][j]=ul[i][j]=0;
}
}
for(int j=m;j>=1;j--){
if(a[i][j]=='*'){
r[i][j]=r[i][j+1]+1;//底边中点向右最大长度
}
else r[i][j]=0;
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<l[i][j]<<' ';
// }
// cout<<'\n';
// }
long long ans=0;
for(int i=1;i<=m;i++){
memset(t,0,sizeof(t));//树状数组清空
vector<vector<int>>del(n+1);
for(int j=n;j>=1;j--){//枚举这一列所有点
if(a[j][i]=='*'){
int delpos=j-min(l[j][i],r[j][i])+1;
if(delpos>=1)del[delpos].push_back(j);//计算失效位置
int pos=min(ur[j][i],ul[j][i])+j-1;//作为顶点的范围
ans+=sum(pos);//统计范围内底边中点数
add(j,1);//作为底边中点插入
}
for(auto &k:del[j]){//删除失效的底边中点
add(k,-1);
}
}
}
cout<<ans;
}
J 计算几何 状压dp
其实没那么难，主要是读懂题意。每次画线都会把当前线上，以及当前线连着的线上所有点都染成一个新的颜色，问最少画几次可以把所有点都染成一个颜色。
观察数据范围，点数只有20个，显然状压。一个比较重要的观察是，每次都从已经染色的点上出发画新线，就是最优做法了，每次都挑未染色的点连线，最后再连起来，画线次数不会比第一种方式少。
那么状态转移就好想了，任何时刻已染色的点，颜色肯定都是一样的，那么枚举所有已染色的点，枚举该点引出的所有直线进行染色，染色后的状态就是染色前的状态并上新画直线对应状态，转移时取最小次数。
我们枚举时用到了所有直线对应的状态，这需要先预处理：两点确定直线枚举所有直线，然后再枚举所有点，判断是否在线上，在的话就把直线对应状态上加上这个点。dp初始化则是所有直线的画线次数为1。
using namespace std;
using i64 = long long;
using Point = complex<i64>;
auto cross(const Point &a, const Point &b) {//叉乘
return imag(conj(a) * b);
}
bool onLine(Point &a, Point &b, Point &c) {
return cross(b - a, c - a) == 0;//叉乘为0判共线
}
int d[30][30],dp[1<<21];
Point a[30];
int main(){
int n;
cin>>n;
for(int i=0;i<(1<<n);i++)dp[i]=n;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
a[i]=Point(x,y);//存点
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){//枚举直线
if(i!=j){
for(int k=0;k<n;k++){//枚举点
if(onLine(a[k], a[j], a[i])){//判断在线上
d[i][j]|=1<<k;//状态加入该点
}
}
}
else{
d[i][j]|=1<<i;//只经过自己一个点的直线
}
dp[d[i][j]]=1;//所有直线染色次数初始化为1
}
}
for(int i=1;i<(1<<n);i++){//枚举染色状态
for(int j=0;j<n;j++){
if(i>>j&1){//枚举状态上已染色点
for(int k=0;k<n;k++){//枚举从该点引出的直线
dp[i|d[j][k]]=min(dp[i|d[j][k]],dp[i]+1);
//转移到染这条线的状态，点集取并
}
}
}
}
cout<<dp[(1<<n)-1];//全染色的最小操作次数
}
K 线段树
一眼就能看出是线段树，但是有三种情况，区间合并的情况有点多，还是很考验码力的。
关键是tag的设计，复杂的合并往往需要很多的tag，该设tag的时候就设，反正tag变多也只是常数变大，但是tag维护的信息可以降低思考的复杂度。换句话说就是减低思维难度，增加码量，这其实是划算的，增加码量无非就是写的时候细心点，多考虑几种特殊情况，但是tag少了可能根本做不出来。
黄色当前堆加一，蓝色新开一堆加一，红色当前堆先翻倍再加一。可以发现有蓝色出现就会新开一堆，后面的操作对当前堆就没用了。那么合并的时候，右区间只有第一个蓝色之前的操作能作用在左区间最后一堆（最后一个蓝色之后）上，后面的操作都可以不管。操作也只有红黄两种，黄色其实没用，因为黄色对个数的贡献在前面就已经算过了，他不会在合并时影响到左区间，红色的个数则需要记录，每一个红色都会让左区间最后一堆翻倍，红色对右区间第一堆的影响其实也在前面合并的时候计算过了，不用管。
那么我们需要一个blue维护是否有蓝色，对于从左往右第一个蓝色之前，最后一个蓝色之后，和两个蓝色之间的数据，需要三个tag分别维护，每个tag都需要包含总个数和红色个数两个量。两个没有蓝色的区间相加，合并时计算规则和有蓝色的不一样，也开一个tag维护。
接下来就是复杂的分类讨论合并，见代码
using namespace std;
#define ll long long
#define db double
#define inf 0x3f3f3f3f
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define rep1(i,x,y) for(int i=(x);i>=(y);i--)
#define pii pair<int,int>
#define ls u<<1
#define rs u<<1|1
#define int ll
const int N=2e5+10;
const int M1=1e9+7,M2=998244353;
ll power(ll a, ll n)//注意a如果为阶乘的话使用ll接收
{
int ret = 1;
while (n)
{
if (n & 1) ret = ret * a%M2;
a = a * a%M2;
n >>= 1;
}
return ret;
}
ll inv(ll x){
return power(x, M2-2);
}
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
int pow2[N];
string s;
struct Data{
int a,b;//总个数和红色个数
};
//直接重载加号可以让线段树内部更简洁
Data operator+(const Data& a,const Data& b){
Data ans={};
ans.a=(a.a*pow2[b.b]+b.a)%M1;//右边的红色会让左边翻倍
ans.b=a.b+b.b;//红色个数直接相加
return ans;
}
struct Node{
int l,r;
ll blue,mid;
Data data,ldata,rdata;//有蓝时,分为ldata,mid,rdata
//没有蓝时就是data
};
Node operator+(const Node& a,const Node& b){
Node ans={};
ans.l=a.l;//边界修改
ans.r=b.r;
if(a.blue&&b.blue){//两边都有蓝
auto t=a.rdata+b.ldata;
ans.ldata=a.ldata;//左左成为左
ans.rdata=b.rdata;//右右成为右
ans.mid=(a.mid+b.mid+t.a)%M1;//左右，右左的和，左中加右中成为中
ans.blue=1;
}
else if(a.blue&&!b.blue){//左边有蓝，右边没有
ans.ldata=a.ldata;//左左成为左
ans.mid=a.mid;//左中成为中
ans.rdata=a.rdata+b.data;//左右加右成为右
ans.blue=1;
}
else if(!a.blue&&b.blue){
ans.ldata=a.data+b.ldata;
ans.mid=b.mid;
ans.rdata=b.rdata;
ans.blue=1;
}
else{//左右都没蓝
ans.data=a.data+b.data;//直接加
}
return ans;
}
struct Tree{
Node tr[N<<2];
void pushup(int u){
tr[u]=tr[ls]+tr[rs];//重载了加号，区间和并就可以直接加
}
// void pushdown(int u){
// if(tr[u].add){
// tr[ls].mx+=tr[u].add;
// tr[rs].mx+=tr[u].add;
// tr[ls].add+=tr[u].add;
// tr[rs].add+=tr[u].add;
// tr[u].add=0;
// }
// }
void build(int u,int l,int r){
tr[u].l=l;
tr[u].r=r;
if(l==r){
if(s[l]=='Y'){
tr[u].data.a=1;
}
else if(s[l]=='R'){
tr[u].data.a=1;
tr[u].data.b=1;
}
else{
tr[u].rdata.a=1;
tr[u].blue=1;
}
return;
}
int mid=(l+r)>>1;
build(ls,l,mid); build(rs,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,char val){
if(tr[u].l>=l&&tr[u].r<=r){
s[l]=val;
Node ans={};
ans.l=l;
ans.r=r;
if(s[l]=='Y'){
ans.data.a=1;
}
else if(s[l]=='R'){
ans.data.a=1;
ans.data.b=1;
}
else{
ans.rdata.a=1;
ans.blue=1;
}
tr[u]=ans;
return ;
}
else{
int mid=(tr[u].l+tr[u].r)>>1;
// pushdown(u);
if(mid>=l) modify(ls,l,r,val);
if(r>mid) modify(rs,l,r,val);
pushup(u);
}
}
Node query(int u,int l,int r){//合并要返回区间节点
if(l<=tr[u].l&&tr[u].r<=r) return tr[u];
// pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(r<=mid)return query(ls,l,r);
if(l>mid)return query(rs,l,r);
return query(ls,l,r)+query(rs,l, r);
}
}t;
void solve(void){
int n,q;
cin>>n>>q;
pow2[0]=1;
rep(i,1,n)pow2[i]=pow2[i-1]*2%M1;
cin>>s;
s="!"+s;
t.build(1,1,n);
while(q--){
int op;
cin>>op;
if(op==1){
int p;
char c;
cin>>p>>c;
t.modify(1,p,p,c);
}
else{
int l,r;
cin>>l>>r;
auto ans=t.query(1,l,r);
cout<<(ans.ldata.a+ans.rdata.a+ans.mid+ans.data.a)%M1<<'\n';
//所有个数都加起来，无意义的都是0，不影响
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int test=1;
// cin>>test;
while(test--){
solve();
}
}
京公网安备 11010502036488号