这一场，题目好多都还不会，sg函数，FFT,DFT啥的都还不会。

B

几何题，给问球是否会掉下，不会球在什么位置

代码：

#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
    //freopen("in.txt","r",stdin);
    double r,a,b,h,o,x,y,z;
    scanf("%lf%lf%lf%lf",&r,&a,&b,&h);
    if(2*r<=b) printf("Drop\n");
    else
    {
        printf("Stuck\n");
        o=atan(2*h/(a-b));
        x=tan(o/2)*r;
        y=x-b/2;
        z=y*tan(o);
        printf("%.10lf\n",z+r);
    }

    return 0;
}

D

给一个01矩阵，给你一个只有2的串，问可以放在01矩阵中0的地方，必须是连续放，不能拆。

思路就是在没一行检查有多少个子串，可以用KMP

代码：

#include <bits/stdc++.h>
using namespace std;
void getnext(string a,int next[])
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<a.size())
    {
        if(j==-1||a[j]==a[i])
        {
            i++;j++;next[i]=j;
        }
        else
        j=next[j];
    }
}
int kmp(string a,string b,int next[])
{
    int i=0,j=0,ans=0;
    while(a[i])
    {
        if(a[i]==b[j]||j==-1)
        {i++;j++;}
        else
        {j=next[j];}
        if(j==b.size())
        {ans++;}
    }
    return ans;
}
int main(){
    int n,m;
    string a[2005];
    string b,c;
    int next[2005];
    while(cin>>n>>m){
        int ans=0;
        for(int i=0;i<n;i++)
            cin>>a[i];
        cin>>b;
        for(int i=0;i<m;i++){
            b[i]-=2;
        }
        getnext(b,next);
        for(int i=0;i<n;i++){
            ans+=kmp(a[i],b,next);
        }
       /* for(int i=0;i<n;i++){
            cout<<next[i]<<endl;
        }*/
       /* cout<<b<<endl;
        cout<<kmp(a[0],b,next)<<endl;*/
        cout<<ans<<endl;
    }
}

F

定义friendly数：连续子串是3的倍数就为friendl，0也算。
问L~R区间，有多少个friendly数，

不是数位DP！！！

枚举之后发现100以后的三位数都是friendly。所以打表
100以前只有这些是unfriendly;

1,4,7,
2,5,8,
11,14,17,
22,25,28,
41,44,47,
52,55,58,
71,74,77,

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100]={1,1,1,2,2,2,3,3,3,4,5,5,6,7,7,8,9,9,10,11,12,13,13,14,15,15,16,17,17,18,19,20,21,22,23,24,25,26,27,28,29,29,30,31,31,32,33,33,34,35,36,37,37,38,39,39,40,41,41,42,43,44,45,46,47,48,49,50,51,52,53,53,54,55,55,56,57,57,58,59,60,61,61,62,63,63,64,65,65,66,67,68,69,70,71,72,73,74,75,76};
ll cou(ll x)
{
    if(x<0)return 0;
    else {
        if(x<100)return dp[x];
        else{
            ll y=x-99+76;
            return y;
        }
    }
}
int main()
{
    int t;cin>>t;
    while(t--){
        ll l,r;cin>>l>>r;
        printf("%lld\n",cou(r)-cou(l-1));
        //printf("%lld %lld\n",cou(r),cou(l-1));
    }
}

G

给你两个长度为n的数组a,b;你可以交换k次数组a中的两个数，求交换后 的最大值。

对于一组 因为是绝对值，所以是交换a数组，其实也就是交换b数组，所以我们就可以通过交换保证，

那我们就要讨论和的大小；

情况一:
不交换的结果：
交换之后的结果：
交换前后的差值：
情况二：:
以此类推可以发现，这种情况交换前后的结果没有增加答案的大小。所以不考虑。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
#define debug(x) cout << #x << ": " << x << endl;

int a[N],b[N];

int main(){;
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    ll ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        if(a[i]>b[i]) swap(a[i],b[i]);//保证B是更大的那个 
        ans+=b[i]-a[i];//求没交换之前的答案 
    }
    sort(a+1,a+1+n);//排序，a的最大减b的最小，答案一定最大 
    sort(b+1,b+1+n);
    for(int i=1;i<=k&&i<=n;i++){
        int res=2*(a[n+1-i]-b[i]);
        if(res>0) ans+=res;
        else break;
    }
    cout<<ans<<endl;
}