2022/5/12

如果a[i]和k前j-1位都相同，第j位aj=0,kj=1,那a[i]就一定比k小了，就用这个结论来做这个题，假设a[i]和k前j-1位都相同，如果kj=0,那么xj只能等于aj，因为如果xj^aj==1，那x^a[i]就比k大了；如果kj等于1，那么xj可以等于aj，这个j往后的位置取什么都无所谓；要是xj等于aj^1说明在第j位也是相同的比较不出大小，继续看下一位；这样x能取值的数是在一个区间里的，我们用差分数组来维护能喝可乐数的修改，最后求前缀和，最大的就是最大能喝的可乐数了；

可乐题解 - QwQ - 洛谷博客 

#include
#define ll long long
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,k,b[2000006],s1[55],s2[55],a[1000006];
void f(ll x){
    memset(s1,0,sizeof(s1));
	memset(s2,0,sizeof(s2));
    ll len1=0,len2=0,kk=k,sum=0;
    while(kk) s2[++len2]=kk%2,kk/=2;
    while(x) s1[++len1]=x%2,x/=2;
    ll len=max(len1,len2);
    for(int i=1;i<=len/2;i++)
        swap(s1[i],s1[len-i+1]),swap(s2[i],s2[len-i+1]);
    for(int i=1;i<=len;i++){
        if(s2[i]==0) sum=sum*2+s1[i];
        else{
               //k1相当于s1[i]后面都取0，k2相当于s1[i]后面都取1
            ll k1=(sum*2+s1[i])*(1<<(len-i)),k2=(sum*2+s1[i]+1)*(1<<(len-i));
            b[k1]++,b[k2]--;
            sum=sum*2+(s1[i]^1);
        }
    }
    b[sum]++,b[sum+1]--;
}
int main(){
	//freopen("in.txt","r",stdin);
    scanf("%lld%lld",&n,&k);
    ll maxx=k;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),maxx=max(maxx,a[i]);
    for(int i=1;i<=n;i++) f(a[i]);
    for(int i=1;i<=maxx*2;i++) b[i]+=b[i-1];//取maxx*2是取一个差分的最大值，sum最大也不超过maxx*2
    ll ans=0;
    for(int i=0;i<=maxx*2;i++) ans=max(ans,b[i]);
    printf("%lldn",ans);
	return 0;
}

这个题看测试数据才过的，也就算不过了，让拳击手尽可能地多，那就让拳击手尽可能地从最小开始，排个序之后，尽可能地减1，减1不行我们就尽可能地加1，这地方和减1的条件有点不同，减1的条件是a[i]-1>0&&tx[a[i]-1]<=0,而加1的条件是a[i]+1<=150001&&tx[a[i]]>=2,因为a[i]的次数大于等于2了，加1总是最优的；

#include
#define ll long long
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,a[150005],tx[150005];
int main(){
	//freopen("in.txt","r",stdin);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),tx[a[i]]++;
    sort(a+1,a+n+1);
   // for(int i=1;i<=n;i++) cout<0&&tx[a[i]-1]<=0) tx[a[i]-1]++,tx[a[i]]--,a[i]--;
        else if(tx[a[i]]>=2&&a[i]+1<=150001) tx[a[i]]--,tx[a[i]+1]++,a[i]++;
    }
    sort(a+1,a+n+1);
    ll m=unique(a+1,a+n+1)-a-1;
    printf("%lldn",m);
	return 0;
}

又是看数据才过的，，，其实一开始就用深搜的话也不会这样了，，，

分成两个点集合，如何一条边完全在一个点集合里的话那这一定是不符合条件的。因为另一个集合两个端点都不包括；我们可以设标记数组vis，两个vector:a,b来记录答案，如果vis[i]=-1说明这个点还没有被放入任意集合中，那么随便给他分配一个，vis[i]=1说明在1集合中，vis[i]=0说明在0集合中，如果读入的边u,v中的u是vis[u]=-1,那我们就采用黑白染色的方式对u及u相连的点更确切地说是u的孩子进行黑白染色，如果u的孩子在染色前就和u的颜色一样，那只能输出-1，如果符合条件最后输出a,b这两个vector就可以了

#include
#define ll long long
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,vis[100005],flag,x[100005],y[100005];
vectora[2],v[100005];
void dfs(ll u,ll fa){
    vis[u]=!vis[fa];
    a[vis[u]].push_back(u);
    //printf("%lld %lldn",u,fa);
    for(int i=0;i 
Lunar New Year and a Wander 
上面的两题都是看了测试数据才过的，这道题直接没想出咋做来，一直在想该如何记录路径，看了题解后发现，这就是一个普普通通的bfs，不需要记录路径，直接广搜就可以了，用优先队列记录的永远都是最优值，还是对bfs的理解不行，，
 
#include
#define ll long long
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,vis[100005],flag;
vectorv[100005];
void bfs(){
    priority_queue,greater >q;
    q.push(1);
    while(!q.empty()){
        ll u=q.top();q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        printf("%lld ",u);
        for(int i=0;i 
农田划分 - 题目 - Daimayuan Online Judge 
可以发现第n块的收益要大于1~n-1块的收益之和，而且两个人的收益是一定不会相等的，所以我们给老大第n块就满足了一部分条件，题目还要求每个人所拥有的田地是联通的，所以要经过点n的田地老二是不能要的，但老二也要尽可能地大，那么从点n相连的点出发也就是从点n的孩子出发，去找一个含有最大的i（除n外）的连通块，将这一部分染成B其他染成A最后输出就行了；
 
#include
#define ll long long
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,cnt,m,ma[300005],vis[300005],maxx,mar;
char s[300005];
vectorv[300005],li[300005];
void bfs(ll u){
    queueq;
    q.push(u);
    while(!q.empty()){
        ll now=q.front();q.pop();
        if(vis[now]!=-1) continue;
        vis[now]=cnt;ma[cnt]=max(ma[cnt],now);
        li[cnt].push_back(now);
        //cout<maxx){
            maxx=ma[cnt];
            mar=cnt;
        }
        for(int i=0;i 
但上述思路和代码都有点繁琐，以至于我wa了4发，，，其实除n外最大的不就是n-1吗，那么我们只要找到n-1所在的连通块都染成B就行了，可以用并查集快速找到连通块，找的过程中我们要把含有n的边给删掉，因为题目保证了所有点都是联通的，不删的话最后的结果就全是B，删掉边之后只能通过n经过的点也不属于n-1的连通块了，所以就可以并查集了；
 
#include
#define ll long long
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,s[300005];
ll findset(ll x){
    return s[x]==x?x:s[x]=findset(s[x]);
}
int main(){
	//freopen("in.txt","r",stdin);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) s[i]=i;
    for(int i=1;i<=m;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        if(u!=n&&v!=n){
            ll x=findset(u),y=findset(v);
            s[x]=y;
        }
    }
    for(int i=1;i<=n;i++)
    if(findset(i)!=findset(n-1)) printf("A");
    else printf("B");
	return 0;
}

 
P7167 [eJOI 2020 Day1] Fountain - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 
这个好像比p5648那题简单点，虽然这题不也是不会，但是比那题好理解，我们用单调栈处理出第i个盘之后第一个比他大的盘，然后to[i][j]表示第i个盘之后第2^j个比他大的盘子，f[i][j]表示第i个盘子一直到第2^j-1个比它大的盘子的容量之和，这两个都可以倍增的求出来，之后就是查询了，倒着查，这样如果有v>f[r][i]说明这个v要大于r后的第2^i-1个比r大的盘,小于r后的第2^i个盘子，所以可以直接定位到to[r][i],这里是改了下f[i][j]的定义使得查询变得简单；
 
题解 P7167 【[eJOI 2020 Day1] Fountain】 - Alex_Wei 的博客 - 洛谷博客
 
#include
#define ll long long
#define lowbit(i) ((-i)&(i))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,to[150005][32],f[150005][32],d[100005],c[100005];
stackst;
int main(){
	//freopen("in.txt","r",stdin);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&d[i],&c[i]);
    for(int i=n;i>=1;i--){
        while(!st.empty()&&d[st.top()]<=d[i]) st.pop();
        to[i][0]=st.empty()?0:st.top();
        f[i][0]=c[i];
        st.push(i);
    }
    for(int j=1;j<=17;j++)
        for(int i=1;i<=n;i++)
        to[i][j]=to[to[i][j-1]][j-1],f[i][j]=f[i][j-1]+f[to[i][j-1]][j-1];
    while(m--){
        ll r,v;
        scanf("%lld%lld",&r,&v);
        for(int i=17;i>=0;i--) if(v>f[r][i]) v-=f[r][i],r=to[r][i];
        printf("%lldn",r);
    }
	return 0;
}

 
P7402 [COCI2020-2021#5] Sjeckanje - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 
这题加上走神的时间大概花了一晚上吧，一开始想的也是dp，但dp太耗时了，然后找题解看到把非单调区间拆成单调区间，这样就可以和差分数组联系上了，每个区间的权值就是b[l+1]+b[l+2]+...+b[r],当然是要加绝对值的，单调递减的话就都是负数了，这个也可以用线段树来维护，t[p][0/1][0/1]代表p端点这段区间是否要左端点和是否要右端点所能得到的最大权值和，合并的时候要注意如果左子区间和右子区间符号不一样的话是不能合并的，这个也就表示子区间只有符号一样才可以相加也就是子区间如果能相加的话那么子区间合并起来也一定得是一个单调区间；
 
[COCI2020-2021#5] Sjeckanje 题解 - LittleYang0531 的博客 - 洛谷博客
 
#include
#define ll long long
using namespace std;
const int N=1e6+5;
int n,m,f[N];
bool vis[N];
int r_find(int r)
{
    if(f[r]==r)
        return f[r];
    f[r]=r_find(f[r]);
    return f[r];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        if(u!=n&&v!=n)
        {
            int fx=r_find(u),fy=r_find(v);
            if(fx==fy)
                continue;
            f[fx]=fy;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(r_find(i)==n-1)
            printf("B");
        else printf("A");
    }
    printf("n");
    return 0;
}