20221009(种)

题目

小朋友的数字

题意

每个人有3个数值，手上的数字，特征值和分数。

• 每个人的特征值是这个人之前（包括这个人）的最大连续子段和。
• 每个人的分数是这个人之前（不包括这个人）的所有人中分数与特征值和的最大值。

思路

​ 我们要求最大分数，而求分数就要求特征值，而特征值就是求最大连续子段和，求最大连续子段和一个\(dp\)就可以完成，\(dp[i]\)表示到第\(i\)个数的最大连续子段和，\(kp[i]\)表示从\(i\)到\(i\)之前的数的最大连续子段和则有:

然后求分数时，只需维护一个最大值即可。

计算过程中可能会爆\(long　long\),大致有三种处理方法。

1. __int128
2. 开一个\(long　long\)类型的二维数组，第一维存一部分数字，第二维存一部分数字，最后求答案时把两个部分拼起来即可。
3. 对答案取模，取模时保存一个模数和一个除数，求答案时复原即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define ll __int128
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
    x=0;int f=0;char c=getchar();
    for(;!isdigit(c);c=getchar())f|=(c=='-');
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=f?-x:x;
}
template<typename T>inline void out(T x){
    if(x<0)x=~x+1,putchar('-');
    if(x>9)out(x/10);
    putchar(x%10^48);
}
const int N=1e6+5;
int n,p;
ll a[N];
ll kp[N],sc[N],b[N];
ll ans,eans;
bool f;
inline ll maX(ll a,ll b){ 
    return a>b?a:b;
}
inline ll abS(ll a){
    return a<0?-a:a;
}
signed main(){
    in(n),in(p);
    eans=ans=-1e18;
    ll sum=-1e18;
    fo(i,1,n){
        in(a[i]);
        kp[i]=i==1?a[i]:maX(kp[i-1]+a[i],a[i]);
        sum=maX(sum,kp[i]);
        b[i]=sum;
    }
    sc[1]=b[1];
    eans=sc[1];
    ans=sc[1]+b[1];
    for(int i=2;i<=n;++i){
        if(b[i-1]+sc[i-1]>ans)ans=b[i-1]+sc[i-1];
        sc[i]=ans;
        eans=maX(eans,ans);
    }
    eans<0?f=1:f=0;
    out(f?-abS(eans)%p:eans%p);
    return 0;
}

涂满它!

IDA*

薇薇位位运算

这里推一手某位名大佬的博客:oWXDo

题目分析

​ 对于一堆数，我们每次可以进行两种运算&和|，即按位与和按位或。对于任意两个数\(a,b\),我们可以让其中一个数变为\(a\)&\(b\),让另外一个数变为\(a\)|\(b\)。我们对它们计算的过程并不会改变他们二进制下\(1\)的总数，而只是把他们二进制下的\(1\)相互交换的过程。这样子操作怎么最大化所有数的平方和呢？其实非常简单。对于\(a^{2}+b^{2}\le(a+b)^{2}\)，并且这里的\(a,b\ge0\)，必然成立。所以我们只需要构造出尽可能让二进制下的\(1\)的个数最多的数即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
    x=0;int f=0;char c=getchar();
    for(;!isdigit(c);c=getchar())f|=(c=='-');
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=f?-x:x;
}
template<typename T>inline void out(T x){
    if(x<0)x=~x+1,putchar('-');
    if(x>9)out(x/10);
    putchar(x%10^48);
}
const int N=1e5+5;
int n,a[N];
int maxlen;
int t[N];
inline void turn(int x){
    int l=0;
    for(;x;x>>=1,++l)
	if(x&1)++t[l];
    return;
}
ll ans;
int tmp;
int main(){
    in(n);
    fo(i,1,n){
	in(a[i]);
	turn(a[i]);
    }
    fo(i,0,21)maxlen=max(maxlen,t[i]);
    for(int i=maxlen;i>=1;--i){
	ll sum=0;
	for(int j=21;j>=0;--j){
	    if(t[j]){
		--t[j];
		sum+=1<<j;
	    }
	}
	ans+=sum*sum;
    }
    out(ans);
    return 0;
}

开车旅行

预处理骗分