B.减成一

Solution

答案为差分数组-1之后仍大于0的数之和。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int a[N],d[N],n;

void solve(){
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]--;
        d[i]=a[i]-a[i-1];
        ans+=max(0,d[i]);
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C.面积

Solution

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;
const double PI = 3.14;

int main(){
    int T;cin>>T;
    while(T--){
        ll x;cin>>x;
        printf("%.2f\n",1.0*x*x+1.57*x*x);
    }
    return 0;
}

E.赛马

Solution

排个序贪心比大小。
贪心方案：

  1. 从我方大的马和敌方大的马开始比，若我方的马比敌方的大，则贡献值+1，换到对方下一匹马，换到我放下一匹马。
  2. 我方最大的马都输了，则换到对方下一匹马，我方不变。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int n,a[N],b[N];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    ll ans=0,pos=n;
    for(int i=n;i>=1&&pos>=1;i--){
        if(a[i]>b[pos]) ans++;
        else i++;
        pos--;
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F.三角形

Solution

最优构造方案fibonacci数列，打个表，二分查表。
坑点：开ull，注意数据溢出。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

ull f[N],n,s[N];

void solve(){
    ull a;cin>>a;
    cout<<upper_bound(s+1,s+1+n,a)-s-1-(a==18446744073709551615u)<<'\n';
}

void init(){
    ull END=18446744073709551615u;
    f[1]=1,f[2]=1,s[1]=1,s[2]=2;
    for(int i=3;s[i]<=END;i++){
        f[i]=f[i-1]+f[i-2];
        s[i]=s[i-1]+f[i];
        if(s[i]<s[i-1]) break;
        n=i;
    }
    s[++n]=18446744073709551615u;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    init();
    while(T--){
        solve();
    }
    return 0;
}

H.直线

Solution

结论题，答案为，最优方案每条线都和别的线相交，则每条线的贡献值为,总共有条线，考虑容斥，同一根线算了两次。

数据范围要用大数，那就写个python吧。

Code

n=int(input())
i=0
while i < n:
    a=int(input())
    print (int(a*(a-1)//2))
    i=i+1

J.最大值

Solution


标答给的是kmp，然而蒟蒻的我还没学过kmp，那就哈希字符串吧。因为最大长度是递增的，所以每次比较已记录值的下一位即可。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e5 + 5;

int n,len;
char s[N];
unsigned long long H[N],P[N],base=131;

unsigned long long calc(int x,int len){
    return H[x+len-1]-H[x-1]*P[len];
}

void solve(){
    cin>>s+1;
    int n=strlen(s+1);
    P[0]=1;
    for(int i=1;i<=n;i++){
        H[i]=H[i-1]*base+s[i]-'a'+1;
        P[i]=P[i-1]*base;
    }
    len=1;
    for(int i=2;i<=n;i++)
        while(H[len]==calc(i,len))    len++;
    cout<<len-1<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}