2020-05-19 17:33 已编辑 The University of New South Wales Java

关注

牛客小白月赛25

AOE还是单体？

$贪心，当能花费x而造成大于等于x点伤害时，优先选择群体攻击$
$当剩余存活的个数大于等于x就能造成大于等于x点伤害$

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll n,x;
ll a[N],mx;

int main(){
    scanf("%lld%lld",&n,&x);
    for(int i = 1;i <= n;i++){
        scanf("%lld",a+i);
    }
    sort(a,a+n);
    ll k = n - x;
    if(k <= 0) k = 0;
    else k = a[k];
    ll ans = k*x;
    for(int i = 1;i <= n;i++){
        a[i] -= k;
        if(a[i] > 0) ans += a[i];
    }
    printf("%lld\n",ans);
    return 0;
}

k-size字符串

$将字符串内连续的字符看成一个连通块$
$肯定是有k/2个连通块是a的，k-k/2个连通块是b的$
$或者，k/2个连通块是b的，k-k/2个连通块是a的$

$不会出现其他情况，因为必须是两种字符的连通块间隔地放置$
$否则两个相同连通块会连成一个连通块，$

$所以一种数量是cnt1 = k/2，另外一种是cnt2 = k - k/2$
$cnt2 >= cnt1,因此第一个连通块的数量只能是cnt2$
$分两种：$
$① 是b分成了cnt2个连通块：$
$就是C(n - 1,cnt1 - 1) * C(m - 1,cnt2 - 1)$
$② 是a分成了cnt2个连通块$
$就是C(n-1,cnt2-1) * C(m - 1,cnt1 - 1)$

$为什么有这个式子？$
$C(n-1,cnt1-1)是将n分成cnt1个连通块的方案，相当于有n个1，n-1个间隔$
$给你放cnt1-1个隔板将它们分成cnt1个数$
$同理C(m-1,cnt2-1)是将m分成cnt2个连通块的方法$
$分好后排列，但是只能cnt2的放第一个然后放cnt1的再放cnt2...$
$所有是C(n - 1,cnt1 - 1) * C(m - 1,cnt2 - 1)$

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 1e5;
ll fac[N + 10],facInv[N + 10];
ll qpow(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll x){
    return qpow(x,mod-2);
}
void init(){
    fac[0] = 1;
    for(int i = 1;i <= N;i++){
        fac[i] = fac[i - 1] * i % mod;
    }
    facInv[N] = inv(fac[N]);
    for(int i = N - 1;i >= 0;i--){
        facInv[i] = facInv[i+1] * (i+1) % mod;
    } 
}
ll C(int n,int m){
    if(m < 0 || m > n) return 0;
    return (fac[n] * facInv[m] % mod ) * facInv[n-m] % mod;
}
int n,m,k;

int main(){
    init();
    scanf("%d%d%d",&n,&m,&k);
    int cnt1 = k/2,cnt2 = k - k/2;
    ll ans = C(n - 1,cnt1 - 1) * C(m - 1,cnt2 - 1) % mod;
    swap(n,m);
    ans = (ans + C(n - 1,cnt1 - 1)*C(m - 1,cnt2 - 1) % mod) % mod;
    printf("%lld\n",ans);
    return 0;    
}

白魔法师

$并查集，将相邻的白点建边，维护每个白点所在集合的大小；$
$答案可能由两种来源：$
$① 不用通过施法得到，即白点集合的最大值；$
$② 通过施法得到，枚举每个黑点，该黑点的所有相邻的白点集合大小之和+1$

#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
vector<int> G[N];
int n,fa[N],sz[N];
char s[N];
int find(int x){
    return fa[x] == x?x:fa[x] = find(fa[x]);
}
void merge(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fy] = fx;
        sz[fx] += sz[fy];
    }
}
int main(){
    scanf("%d%s",&n,s + 1);
    for(int i = 1;i <= n;i++) fa[i] = i,sz[i] = 1;
    for(int i = 1,u,v;i < n;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
        if(s[u] == s[v] && s[u] == 'W') merge(u,v);
    }
    int mx = 0;
    for(int u = 1;u <= n;u++){
        int res = 1;
        if(s[u] == 'W') res = sz[find(u)];
        else{
            for(int i = 0;i < G[u].size();i++){
                int v = G[u][i];
                if(s[v] == 'W') res += sz[find(v)];
            }
        }
        mx = max(res,mx);
    }
    printf("%d\n",mx);
    return 0;
}

抽卡

$算反面，算抽不到自己想要的卡的概率p_i$
$最后答案为1-p_i，在取模意义下是(1 - p_i + mod) \% mod$
$在第i个卡池抽不到自己想要卡片的概率是x_i = \frac{a_i-b_i}{a_i}$
$抽完所有卡池都抽不到自己想要卡片的概率：p_i = \prod_{i=1}^n x_i$
$模以下x_i = (a_i - b_i) * inv(a_i)$

#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const ll mod = 1e9 + 7;
ll qpow(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a %mod;
        a = a*a % mod;
        b >>= 1;
    }
    return res%mod;
}
ll inv(ll x){
    return qpow(x,mod-2);
}
ll a[N],b[N];
int n;
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%lld",a+i);
    for(int i = 1;i <= n;i++) scanf("%lld",b+i);
    ll res = 1;
    for(int i = 1;i <= n;i++){
        res = (res * (a[i]-b[i]) % mod) * inv(a[i]) % mod;
    }
    res = (1 - res + mod) % mod;
    printf("%lld\n",res);
    return 0;
}

点击消除

$开个栈模拟，一个个地往后扫字符，如果栈为空或者该字符与当前栈顶元素不相同：直接入栈$
$否则一直找到与当前栈顶不同的字符，如果相同字符个数为偶数就pop栈顶，否则保留$

#include <cstdio>
#include <stack>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 3e5+10;
char str[N];
struct stack{
    char a[N];
    int l = 0;
    void push(char x){
        a[++l] = x;
    }
    char top(){
        return a[l];
    }
    void pop(){
        l--;
    }
    bool empty(){
        if(l > 0) return 0;
        return 1;
    }
}s;
int main(){
    scanf("%s",str);
    s.push(str[0]);
    for(int i = 1;i < strlen(str);){
        if(s.empty()){
            s.push(str[i]);
            i++;
        }else if(str[i]!=s.top()){
            s.push(str[i]);
            i++;
        }else{
            char ch = s.top();
            int be = i - 1,en;
            do{
                i++;
            }while(i<strlen(str)&&str[i]==s.top());
            en = i - 1;
            i = en + 1;
            if(( (en - be + 1)%2==0 )&&!s.empty()) s.pop();
        }
    }
    if(s.empty()) puts("0");
    else{
        char ans[N];
        int idx = 0;
        while(!s.empty()){
            ans[++idx] = s.top();
            s.pop();
        } 
        for(int i = idx;i > 0;i--){
            printf("%c",ans[i]);
        }
        puts("");
    }
    return 0;
}

疯狂的自我检索者

$最低就把未知的全当成1，最高就把未知的全当成5$

#include <cstdio>
#include <iostream> 
using namespace std;
const int N = 2e5 + 10;
double sum;
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n-m;i++){
        double x;scanf("%lf",&x);
        sum += x;
    }
    double mx = sum + m*5,mi = sum + m*1;
    mx = mx / (1.0*n),mi = mi / (1.0*n);
    printf("%.5f %.5f\n",mi,mx);
    return 0;
}

解方程

$f(x) = x^a + b*lnx 是个单调递增函数，二分查找，在查找过程中如果fabs(cal(mid) - c)小于1e-7直接break掉$

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int a,b,c;
const double eps = 1e-7;
double cal(double x){
    double res = pow(x,a) + b*log(x);
    return res;
}
int main(){
    scanf("%d%d%d",&a,&b,&c);
    double l = 0,r = 1e9;
    double ans = -1;
    while(r - l > eps){
        double mid = (l + r)/2;
        if(fabs(cal(mid) - c) < eps){
            ans = mid;
            break;    
        }else if(cal(mid) >= c){
            ans = mid;
            r = mid;
        }else l = mid;
    }
    printf("%.14f\n",ans);
}

神奇的字母（二）

$开个桶，统计次数最多$

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
string str;
int num[30];
int main(){
    while(cin>>str){
        for(int i = 0;i < str.size();i++){
            num[str[i] - 'a']++;
        }
    }
    int mx = 0,mx_ch = -1;
    for(int i = 0;i < 26;i++){
        if(num[i] > mx){
            mx = num[i];
            mx_ch = i;
        }
    }
    printf("%c\n",(char)('a' + mx_ch));
    return 0;
}

十字爆破

$用col[i]表示第i行元素之和，row[i]表示第i列元素之和$
$爆破(i,j)就是 col[i] + row[j] - val[i][j]$
$val[i][j]转成一维就是val[i*m+j]$

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll row[N],col[N];
int n,m;
ll a[N];
int num(int i,int j){
    return (i-1)*m + j;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            scanf("%lld",&a[num(i,j)]);
            col[i] = col[i] + a[num(i,j)];
            row[j] = row[j] + a[num(i,j)]; 
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            printf("%lld ",col[i]+row[j]-a[num(i,j)]);
        }
        puts("");
    }
    return 0;
}

异或和之和

$统计二进制每一位上的贡献，只有1\wedge1\wedge1和0\wedge0\wedge1才会产生贡献$
$首先统计每个二进制位上1出现的次数a_i和0出现的次数b_i$
$对于第i位的贡献就是(1ll<<i) * (C(a_i,3) + a_i*C(b_i,2))$

#include <cstdio>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int num[64][2];


ll quick_mod(ll a, ll b){
    ll ans=1;
    a%=mod;
    while(b){
        if(b&1){
            ans=ans*a%mod;
            b--;
        }
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
ll C(ll n,ll m){
    if(m>n) return 0;
    ll ans=1;
    for(int i=1;i<=m;i++){
        ll a=(n+i-m)%mod;
        ll b=i%mod;
        ans=ans*(a*quick_mod(b,mod-2)%mod)%mod;
    }
    return ans;
}

int main(){
    int n;scanf("%d",&n);
    for(int i = 0;i < n;i++){
        ll x;scanf("%lld",&x);
        for(int j = 0;j < 64;j++){
            ll k = x % 2;
            num[j][k]++;
            x >>= 1ll;
        }
    }
    ll ans = 0;
    for(ll i = 0;i < 64;i++){
        ans = (ans + ((1ll<<i) % mod) * (C(num[i][1],3) + C(num[i][0],2)*C(num[i][1],1) % mod) % mod) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}