当前位置：网站首页>Atcoder beginer contest 169 (B, C, D unique decomposition, e mathematical analysis f (DP))

Atcoder beginer contest 169 (B, C, D unique decomposition, e mathematical analysis f (DP))

2022-07-02 16:51:00 【ccsu_ deer】

Topic link

B - Multiplication 2
practice ： The subject is very simple , But all kinds of postures are not given A It's disgusting ,__int128 wa,ull also wa, Last use java Da Shucai A, I'm impressed .
Looking at other people's code, I found , It uses a kind of Judge explosion long long Methods , See the code .

c++ Code ：

       
        #include <bits/stdc++.h>
        
using namespace std;
        
using ll = long long;
        

        
ll solve() {
        
    ll N, a;
        
    cin >> N;
        
    vector<ll> A(N);
        
    for ( int i = 0; i < N; i++ ) {
        
        cin >> A[i];
        
        if ( A[i] == 0 ) return 0;//????? I returned before I finished typing ？
        
    }
        
    ll mx = 1e18;
        
    ll m = 1, p = 1;
        
    for ( int i = 0; i < N; i++ ) {
        
        m *= A[i];
        
        if ( m < p || m > mx ) return -1;// It's smaller than before , It's explosion longlong 了 
        
        p = m;
        
    }
        
    return m;
        
}
        

        
int main() {
        
    auto ans = solve();
        
    cout << ans << "\n";
        
    return 0;
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.

Java Code ：

       
        import java.math.BigInteger;
        
import java.util.Scanner;
        

        
public class Main {
        
    public static void main(String args[]){
        
        Scanner sc=new Scanner(System.in);
        
        int n=sc.nextInt();
        
        BigInteger N=new BigInteger("1000000000000000000");
        
        BigInteger ans=new BigInteger("1");
        
        BigInteger n0=new BigInteger("0");
        

        

        
        int flag=1;
        
        int num=1;
        
        for(int i=1;i<=n;++i){
        
            BigInteger x=sc.nextBigInteger();
        
            if(x.compareTo(n0)==0) num=0;
        
            if(flag==0) continue;
        
            ans=ans.multiply(x);
        
            if(ans.compareTo(N)>0) {
        
                flag=0;
        
            }
        
        }
        

        
        if(num==0) System.out.println(0);
        
        else if(ans.compareTo(N)>0||flag==0) System.out.println("-1");
        
        else System.out.println(ans);
        
    }
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.

C - Multiplication 3
I was disgusted by these two questions ,-0.5 wa round also wa, Last use java Of ROUND_DOWN Yes ..

       
        import java.math.BigDecimal;
        
import java.math.BigInteger;
        
import java.util.Scanner;
        

        
public class Main {
        
    public static void main(String args[]){
        
        Scanner sc=new Scanner(System.in);
        

        

        
        BigDecimal a,b;
        
        a=sc.nextBigDecimal();
        
        b=sc.nextBigDecimal();
        
        BigDecimal ans=a.multiply(b);
        

        

        

        
        System.out.println(ans.setScale(0, BigDecimal.ROUND_DOWN));
        
    }
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.

D - Div Game
The only way is to decompose it .

       
        #pragma GCC optimize(2)
        
#include<bits/stdc++.h>
        
#define ll long long
        
#define maxn 1005
        
#define inf 1e9
        
#define pb push_back
        
#define rep(i,a,b) for(int i=a;i<=b;i++)
        
#define per(i,a,b) for(int i=a;i>=b;i--)
        
using namespace std;
        

        
inline ll read()
        
{
        
    ll x=0,w=1; char c=getchar();
        
    while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
        
    while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
        
    return w==1?x:-x;
        
}
        

        

        
int main()
        
{
        
    ll n=read();
        
    int ans=0;
        
    for(ll i=2;i*i<=n;++i){
        
        if(n%i==0){
        
            int num=0;
        
            while(n%i==0) num++,n=n/i;
        

        
            int l=1,r=1000,t=0;
        
            //printf("i:%lld num:%d\n",i,num);
        

        
            while(l<=r){
        
                int mid=l+r>>1;
        
                int res=mid*(mid+1)/2;
        
                if(res>num) r=mid-1;
        
                else t=mid,l=mid+1;
        
            }
        
            //printf("t:%d\n",t);
        
            ans+=t;
        

        
        }
        
    }
        
    if(n!=1) ans++;
        

        
    printf("%d\n",ans);
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.
        33.
        34.
        35.
        36.
        37.
        38.
        39.
        40.
        41.
        42.
        43.
        44.
        45.
        46.

E - Count Median
The question ： Here you are. n Intervals [li,ri] n Number a[i] Respectively from the n Choose one of the intervals , Ask the number of different median of the formed sequence
The solution comes from b Station boss ： link 
practice ： I feel like I've seen this type of question more than four times , And different problems have different solutions , Or it's a column formula Continuous interval derivation or sum （ The last question of a practice match of Niuke ）, Or it's the same as this question , Mathematical analysis
（ccpc wannfly A question in the training camp replay ： Expected inverse ordinal number ）
 Cattle challenge 36 Sequence 
Another one forgot where it was .
The idea of this question is probably
For one x Can it become the median , What are the necessary and sufficient conditions for judging him .
The video said the conclusion ：
about n For odd numbers ,
1、 Right endpoint Less than x Of Section No more than n/2+1 individual ,
2、 Left end point Greater than x Of Section No more than n-(n/2)=n/2+1
about n It's even
1、 Using the above method, we will find two legal intervals
[a1,b1] [a2,b2] because n The median number is The sum of the middle two numbers /2 So the legal range here is b1+b2-(a1+a2)+1
So how to find these x Well ？ For the left endpoint set a Make a sequence , The intermediate number satisfies the necessary and sufficient condition , Right endpoint set b Also similar

       
        #include <iostream>
        
#include <cstdio>
        
#include <algorithm>
        
#include <map>
        
using namespace std;
        
long long a[200010], b[200010];
        
int n;
        
int main() {
        
    cin >> n;
        
    for (int i = 1; i <= n; i++) {
        
        cin >> a[i] >> b[i];
        
    }
        
    sort(a + 1, a + n + 1);
        
    sort(b + 1, b + n + 1);
        
    if (n % 2) {
        
        //printf("b:%lld a:%lld\n",b[n/2+1],a[n/2+1]);
        
        cout << b[n / 2 + 1] - a[n / 2 + 1] + 1;
        
    } else {
        
        cout << b[n / 2] + b[n / 2 + 1] - a[n / 2] - a[n / 2 + 1] + 1;
        
    }
        
    return 0;
        
}
        
/*
        
7
        
1 3
        
2 4
        
5 8
        
6 9
        
7 10
        
12 14
        
13 15
        
*/
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.

F - Knapsack for All Subsets
practice ： It's very watery if you don't consider subsets dp set up dp[i][j] For the former i The sum of item subsets is j Number of alternatives .
Transfer equation ：
for(int j=s;j>=a[i];--j){ add(dp[i][j],dp[i-1][j-a[i]]); }
However, this problem is to find all subsets Ask the above question again .
It's also very simple . set up dp[i][j] For the former i The sum of item subsets is j Number of alternatives . Every time I add i dp[i][j]=dp[i-1][j]*2.
Why take 2 Well , Because of the new a[i] choose It can form a subset with all the previous subsets , if a[i] No election , Is to inherit the previous , That's by 2 了 .

       
        #pragma GCC optimize(2)
        
#include<bits/stdc++.h>
        
#define ll long long
        
#define maxn 1005
        
#define inf 1e9
        
#define pb push_back
        
#define rep(i,a,b) for(int i=a;i<=b;i++)
        
#define per(i,a,b) for(int i=a;i>=b;i--)
        
using namespace std;
        
const ll mod=998244353;
        
inline ll read()
        
{
        
    ll x=0,w=1; char c=getchar();
        
    while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
        
    while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
        
    return w==1?x:-x;
        
}
        
const int N=3e3+10;
        
ll dp[N][N];
        
int a[N],n,s;
        
void add(ll &x,ll y)
        
{
        
    x=(x+y)%mod;
        
}
        
int main()
        
{
        
    n=read(),s=read();
        
    rep(i,1,n) a[i]=read();
        
    dp[0][0]=1;
        
    rep(i,1,n)
        
    {
        
        for(int j=0;j<=s;++j) dp[i][j]=dp[i-1][j]*2%mod;
        

        
        for(int j=s;j>=a[i];--j){
        
            add(dp[i][j],dp[i-1][j-a[i]]);
        
        }
        
    }
        
    printf("%lld\n",dp[n][s]);
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.
        33.
        34.
        35.
        36.
        37.
        38.
        39.