2022/7/18-7/19

        昨天做的题太少了，比完赛后看了半天题解都没看懂，今天又看了半天才把i题看懂，今天多做了点思维题补一下 

D-Mocha and Railgun_数学​​​​​​

Q点一定是要放在直径上破坏的墙壁才能是最大，但是我们硬把Q放在水平轴的那条直径上就错了，应该是OQ相连的那条直径才对，因为把OQ放在水平轴上容易计算，所以借Q的坐标算出Q在水平轴上的新的Q的x坐标，之后求弧长就可以了

#include 
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
double pi=acos(-1.0),eps=1e-8;
ll t;
double r,x,y,d;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lf%lf%lf%lf",&r,&x,&y,&d);
        x=sqrt(x*x+y*y);
        if((x-d)*(x+d)-0>=eps){
            double b=acos((abs(x)+d)/r),c=asin((abs(x)-d)/r);
            printf("%.12f\n",r*(pi/2.0-b-c));
        }
        else{
            double b=asin((d+abs(x))/r),c=asin((d-abs(x))/r);
            printf("%.12f\n",r*(b+c));
        }
    }
    return 0;
}

C - Qpwoeirut And The City

n是奇数的话就只能从第二个开始隔一个加一个一直加到n-1个，n是偶数的话可以有一次跳过的机会，即可以有一次是隔两个加一个，昨天用dp没搞出来，今天一想其实维护两个前缀和就够了，一个从第一个开始隔一个加一个，另一个从第n-1个开始隔一个加一个，然后枚举跳过的位置最后输出最小就可以

#include 
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
double pi=acos(-1.0),eps=1e-8;
ll t,n,h[100005],su1[100005],su2[100005],a[100005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
        for(int i=2;imax(0LL,max(h[i-1],h[i+1])-h[i]+1);
        if(n&1){
            ll ans=0;
            for(int i=2;i2) ans+=a[i];
            printf("%lld\n",ans);continue;
        }
        for(int i=2;i
            if(i&1) su1[i]=su1[i-1];else su1[i]=su1[i-1]+a[i];
        }
        for(int i=n-1;i>=2;i--){
            if(i&1) su2[i]=su2[i+1]+a[i];else su2[i]=su2[i+1];
        }
        ll ans=1e18,sum=0;
        for(int i=2;i
                //cout<
            ans=min(ans,su1[i-1]+su2[i+1]);
        }
        printf("%lld\n",ans);
        for(int i=0;i<=n;i++) a[i]=su1[i]=su2[i]=0;
    }
    return 0;
}

​​​​​​I-Chiitoitsu_"蔚来杯"2022牛客暑期多校训练营1 dp 

不该这么早就开始补题的，题解太少而且质量太差，讲的磕磕绊绊，听的稀里糊涂，真的非常难受

首先最优策略就是如果摸到的牌能和已有的单牌凑成一对就保留，否则就扔掉

重点是状态方程(图片来自牛客)

手中还有s张单牌，牌堆还有r张时的期望次数

因为无论是哪一个阶段都是要先摸一张牌，所以一开始要加1。s=1时，如果一次就摸到了那次数就是开始的那个1，否则就要加上没摸到的期望的次数；

s>1时就需要加上没摸到的次数和摸到凑成一对的次数，这个s-2我理解的是摸到一张牌后能够凑成对子保留下来单牌数量加1，但是这个刚摸到的牌可以和手里的单牌凑成一对，所以要-2。

2022牛客多校联赛第一场 题解_Frank_Star的博客-CSDN博客

#include 
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
double pi=acos(-1.0),eps=1e-8;
ll t,dp[205][205];
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 getinv(ll a){return qpow(a,mod-2);}
string s;
void init(){
    dp[1][3]=1;
    for(int i=1;i<=13;i+=2){
        for(int j=4;j<=123;j++){
            if(i==1) dp[i][j]=(1+((j-3)*getinv(j)%mod)*dp[1][j-1]%mod)%mod;
            else dp[i][j]=(1+(3*i*getinv(j)%mod)*dp[i-2][j-1]%mod+((j-3*i)*getinv(j)%mod)*dp[i][j-1]%mod)%mod;
        }
    }
}
int main(){
    cin>>t;
    ll ca=0;
    init();
    //for(int i=1;i<=13;i+=2) cout<
    while(t--){
        cin>>s;
        mapmp;
        for(int i=0;isize();i+=2){
            mp[s.substr(i,2)]++;
        }
        ll cnt=0;
        for(auto x:mp){
            if(x.second==1) cnt++;
        }
        printf("Case #%lld: %lld\n",++ca,dp[cnt][123]);
    }
 
    return 0;
}

Chopping Carrots (Hard Version)

        正解应该是整除分块的思想，但是看的第一篇题解看了两个多小时愣是没看明白，最后幸好找到了一篇救命的，一开始让p[i]都为k，那么得出来的maxx和minn都是最小的，为了让maxx-minn尽可能的小我们可以尽可能的让minn变大，方法就是让p[i]变大，让p[i]变大的方法就可以借助分块，让x[i](x[i]是a[i]/p[i]）变大，然后求出p[i]，在通过新的p[i]求出x[i]，在这个过程中不断更新ans，有时候x[i]可能会超过maxx，就更新maxx，直到p[i]==1不能在变小就结束循环，复杂度是可以过的，因为对于一个a[i]来说，得出的除数是小于根号a[i]的，所以复杂度大概也就是n*根号n，不会超时

Codeforces Round #809 (Div. 2)(A~D2) - 知乎 (zhihu.com)

#include 
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
double pi=acos(-1.0),eps=1e-8;
ll t,n,k,a[100005],x[100005],p[100005];
struct node{
    ll v,id;
    bool operator<(const node &b)const{
        return b.v
    }
};
priority_queueq;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            p[i]=k;
            x[i]=a[i]/k;
        }
        sort(x+1,x+n+1);
        ll maxx=x[n],ans=x[n]-x[1];
        for(int i=1;i<=n;i++) q.push(node{x[i],i});
        while(1){
            ll u=q.top().id;
            q.pop();
            ans=min(ans,maxx-x[u]);
            if(!ans) break;
            x[u]++;
            if(p[u]==1) break;
            p[u]=a[u]/x[u];
            x[u]=a[u]/p[u];
            maxx=max(maxx,x[u]);
            q.push(node{x[u],u});
        }
        printf("%lld\n",ans);
    }
    return 0;
}

1562C - Rings

不难的一道题，截取的两个字符串长度要大于n/2，并且化为十进制后第一个要是第二个的非负整数倍，那我们先考虑原字符串里有0的情况，如果有0的话，一个字符串从这个0开始一直向左或向右（哪边能取取哪边）取上一半+1的长度，另一个取上一半的长度就满足条件了；没0的话就是全1，那么各取一半就可以了

#include 
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
double pi=acos(-1.0),eps=1e-8;
ll t,n;
string s;
int main(){
    scanf("%lld",&t);
    while(t--){
        cin>>n>>s;s=" "+s;
        ll ma=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='0'){ma=i;break;}
        }
        if(ma){
            if(ma<=(n+1)/2) printf("%lld %lld %lld %lld\n",ma,n,ma+1,n);
            else printf("%lld %lld %lld %lld\n",1,ma,1,ma-1);
        }
        else{
            printf("%lld %lld %lld %lld\n",1,n/2,n/2+1,n/2+n/2);
        }
    }
    return 0;
}

Vasya and Petya's Game

从2开始看，如果一个数可以被前面两个数的乘积表示那么这个数也就没有出现的必要了，所以统计好每对数是否出现，判断一个数是否能被表示，最后输出不能被表示的数就可以了

#include 
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=1e9+7;
double pi=acos(-1.0),eps=1e-8;
ll n;
vectorv;
map,ll>mp;
int main(){
    scanf("%lld",&n);
    if(n==1){
        printf("0\n");
        return 0;
    }
    for(int i=2;i<=n;i++){
        ll flag=0;
        for(int j=2;j
            if(i%j==0&&i/j>j){
                ll x=i/j;
                if(x%j==0) continue;
                if(mp[{i,i/j}]) continue;
                mp[{i,i/j}]++;flag=1;break;
            }
        }
        if(!flag) v.push_back(i);
    }
    cout<size()<
    for(int i=0;isize();i++) cout<" ";
    return 0;
}