大吉大利

Solution

位运算常用的优化技巧就是按位计算。用 表示第 位为 的数的个数。由与运算的性质可以得到，两个数二进制第 位都为 时，会使答案加 。因此便可以边读入边处理，最后将答案乘 并加上数本身即可。

时间复杂度：

Code

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn],sum[31],p[31];
long long ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    p[0]=1;
    for(int i=1;i<=30;i++)
        p[i]=p[i-1]*2;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=30;j++)
            if((a[i]>>j)&1){
                ans+=sum[j]*p[j];
                sum[j]++;
            }
    ans*=2;
    for(int i=1;i<=n;i++)
        ans+=a[i];
    cout<<ans;
    return 0;
}

三角形周长和

Solution

此处的边长等于两点间的曼哈顿距离。一条边会在 个三角形中出现，按边统计答案即可。

时间复杂度：

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
const int maxn=1e3+10;
const int mod=998244353;
int n,x[maxn],y[maxn];
ll ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            ans=(ans+(abs(x[i]-x[j])%mod+abs(y[i]-y[j])%mod)%mod*(n-2))%mod;
    cout<<ans;
    return 0;
}

操作集锦

Solution

看到题应该是一道 题。

首先设计状态：我们可以发现两个状态量，分别是当前已处理的位数 与当前已选择的位数 。若不考虑重复，则有

即选与不选两种情况。

题目要求本质不同，所以需要减去重复的情况。考虑什么时候会重复：设 位和 位字母相同，且 。容易发现凡是 加上的情况， 都会加上。也就是说 真包含于 。所以将 减去即可。具体来说，设 表示字母 的上一个位置，则

特别地，有 。

时间复杂度：

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
const int maxn=1e3+10;
const int mod=1e9+7;
ll n,k,f[maxn][maxn],p[26];
string s;
int main(){
    cin>>n>>k>>s;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=1;
        for(int j=1;j<=k;j++){
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
            if(p[s[i-1]-'a'])
                f[i][j]=(f[i][j]+mod-f[p[s[i-1]-'a']-1][j-1])%mod;
        }
        p[s[i-1]-'a']=i;
    }
    cout<<f[n][k];
    return 0;
}

斩杀线计算大师

Solution

第一眼看到以为是一道 题，但是需要枚举其中一项，如果数据强的话会被卡掉。

对于这种给定序列 和数字 ，询问是否能被表示的题目，有一种更好地通法：同余最短路。

设 表示在模一个数（不妨设为 ）的意义下余 的最小能被表示的数。如果感觉很绕，举个栗子： .那么在模 意义下，。

然后，就可以使用 算法求出 数组。这样做的原理是：若 可以被表示，则 一定可以被表示（加若干个 得到）。即 ， 。若 ，则 可以被表示。由于题目要求输出方案数，所以维护一个数组 储存转移到这个状态时选择的哪个数即可。

时间复杂度：

一道很好的同余最短路练习题：Sums

Code

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=1e5+10;
ll a,b,c,k,ans[4],dis[maxn],vis[maxn],nxt[maxn];
priority_queue<pair<int,int> >q;
void Dijkstra(){
    memset(dis,0x7f,sizeof(dis));
    dis[0]=0;
    q.push(make_pair(0,0));
    ll u;
    while(!q.empty()){
        u=q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        if(dis[(u+a)%a]>dis[u]+a){
            dis[(u+a)%a]=dis[u]+a;
            nxt[(u+a)%a]=a;
            q.push(make_pair(-dis[(u+a)%a],(u+a)%a));
        }
        if(dis[(u+b)%a]>dis[u]+b){
            dis[(u+b)%a]=dis[u]+b;
            nxt[(u+b)%a]=b;
            q.push(make_pair(-dis[(u+b)%a],(u+b)%a));
        }
        if(dis[(u+c)%a]>dis[u]+c){
            dis[(u+c)%a]=dis[u]+c;
            nxt[(u+c)%a]=c;
            q.push(make_pair(-dis[(u+c)%a],(u+c)%a));
        }
    }
}
int main(){
    cin>>a>>b>>c>>k;
    Dijkstra();
    ll d=dis[k%a];
    while(nxt[d%a]){
        if(nxt[d%a]==a)
            ans[1]++;
        else if(nxt[d%a]==b)
            ans[2]++;
        else
            ans[3]++;
        d-=nxt[d%a];
    }
    d=ans[1]*a+ans[2]*b+ans[3]*c;
    ans[1]+=(k-d)/a;
    cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3];
    return 0;
}