河南理工2019暑期选拔赛————我好菜

浅浅的花香味﹌ 2021-11-02 12:00 278阅读 0赞

### 文章目录 ###

*  \[Problem A 小L的项链切割\](http://acm.zzuli.edu.cn/problem.php?id=1526)
 *  \[Problem B 小L的试卷\](http://acm.zzuli.edu.cn/problem.php?id=1527)
 *  \[Problem C 小L记单词\](http://acm.zzuli.edu.cn/problem.php?id=2041)
 *  \[Problem D 小L的取膜算式\](http://acm.zzuli.edu.cn/problem.php?id=1528)
 *  \[Problem E 小L玩滚球游戏\](http://acm.zzuli.edu.cn/problem.php?id=1530)
 *  \[Problem F 小L的区间求和\](http://acm.zzuli.edu.cn/problem.php?id=1531)
 *  \[Problem G 小L的随机数\](http://acm.zzuli.edu.cn/problem.php?id=1532)
 *  \[Problem H 小L的直线\](http://acm.zzuli.edu.cn/problem.php?id=1533)
 *  \[Problem I 小L的长方形\](http://acm.zzuli.edu.cn/problem.php?id=1534)

点击题目即可查看原题  
这次的题目都是经典题，  
我是个猪吧？

# [Problem A 小L的项链切割][Problem A _L] #

这题dp

把这一串字符串分成若干个回文串，问切割的次数  
也就是问最少能分几串  
因为 n < = 1000 n<=1000 n<=1000,所以想应该可以 O ( n 2 ) O(n^2) O(n2)  
刚开始我是直接找这个串的回文串有多少个，WA, 我又反着找，求最小的，还是wa。就是没有想到dp

令dp\[i\]表示从字符串从位置1到位置 i ，最少要切割多少次

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    using namespace std;
    const int MAXN = 1e3+7;
    int dp[MAXN];
    char s[MAXN];
    
    bool check(char *s,int l,int r) {
        
            while(l<=r) {
        
                    if(s[l]!=s[r])
                            return false;
                    l++;
                    r--;
            }
            return true;
    }
    
    int main() {
        
            // freopen("../in.txt","r",stdin);
            int t;
            scanf("%d",&t);
            while(t--) {
        
                    scanf("%s",s+1);
                    int len = strlen(s+1);
                    memset(dp,0,sizeof(dp));
                    for(int i=1;i<=len;++i) {
        
                            dp[i] = MAXN;
                            for(int j=1;j<=i;++j) {
        
                                    if(check(s,j,i)) {
        
                                            if(j==1)
                                                    dp[i] = 1;
                                            else
                                                    dp[i] = min(dp[i],dp[j-1]+1);
                                    }
                            }
                    }
                    printf("%d\n",dp[len]-1);
            }
            return 0;
    }

# [Problem B 小L的试卷][Problem B _L] #

这题二分

// #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define lp rt<<1
    #define rp rt<<1|1
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
    
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 2e4+7;
    int a[MAXN];
    int l,r;
    int total,num;
    int n,k;
    bool judge(int x) {
        
            for(int i=0;i<n;++i) {
        
                    if(total+a[i]<=x)       total += a[i];
                    else    total = a[i], num++;
            }
            return num>=k;
    }
    
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
    
            while(cin>>n>>k) {
        
                    l = r = 0;
                    for(int i=0;i<n;++i) {
        
                            cin>>a[i];
                            r += a[i];
                            l = max(l,a[i]);
                    }
                    while(l<=r) {
        
                            int mid = (l+r)>>1;
                            total = num = 0;
                            if(judge(mid)) l = mid+1;
                            else    r = mid-1;
                    }
                    cout<<l<<endl;
            }
            return 0;
    }

# [Problem C 小L记单词][Problem C _L] #

这题水

# [Problem D 小L的取膜算式][Problem D _L] #

这题费马小定理

# [Problem E 小L玩滚球游戏][Problem E _L] #

这题思维，我做过原题

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<bitset>
    #include<set>
    #include<vector>
     
     
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
     
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e5+7;
     
    ll p[MAXN];
     
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ll n,t;
            while(~scanf("%lld %lld",&n,&t)){
        
                    for(int i=0;i<n;++i){
        
                            ll x,y;
                            scanf("%lld %lld",&x,&y);
                            p[i] = x + y * t;
                    }
                    ll num = n;
                    for(int i=n-1;i>0;--i){
        
                            if(p[i-1]>=p[i]){
        
                                    p[i-1] = p[i];
                                    num--;
                            }
                    }
                    printf("%lld\n",num);
            }
     
            return 0;
    }
     
    /**************************************************************
        Problem: 1530
        User: 311709001223
        Language: C++
        Result: 正确
        Time:34 ms
        Memory:2432 kb
    ****************************************************************/

# [Problem F 小L的区间求和][Problem F _L] #

这题…,我傻逼

// #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define lp rt<<1
    #define rp rt<<1|1
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
     
    typedef long long ll;
    typedef pair<int ,int> P;
     
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e6+7;
    int a[MAXN];
    ll sum[MAXN];
    int p[MAXN];
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
            int n,k;
            while(~scanf("%d %d",&n,&k)) {
        
                    sum[0] = 0;
                    int ans = 0;
                    memset(p,0,sizeof(p));
                    for(int i=0;i<n;++i) {
        
                            scanf("%d",&a[i]);
                            sum[i+1] = sum[i]+a[i];
                            sum[i+1] %= k;
                            if(sum[i+1]==0) {
        
                                    ans = max(ans,i+1);
                                    continue;
                            }
                            if(p[sum[i+1]]==0) p[sum[i+1]] = i+1;
                            ans = max(ans, i+1-p[sum[i+1]]);
                    }
                     printf("%d\n",ans);
            }
            return 0;
    }
     
    /**************************************************************
        Problem: 1531
        User: 311709001223
        Language: C++
        Result: 正确
        Time:8 ms
        Memory:17276 kb
    ****************************************************************/

# [Problem G 小L的随机数][Problem G _L] #

这题傻逼

# [Problem H 小L的直线][Problem H _L] #

这题傻逼

// #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define lp rt<<1
    #define rp rt<<1|1
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
     
    typedef long long ll;
    // typedef pair<int ,int> P;
     
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 222;
    int x[MAXN],y[MAXN];
    double P[MAXN*MAXN];
    double p(int i,int j) {
        
            int dx = x[i] - x[j];
            int dy = y[i] - y[j];
            if(dx)
                    return 1.0*dy/dx;
            else
                    return INF;
    }
    int main(){
        
            int n;
            scanf("%d",&n);
            for(int i=0;i<n;++i)
                    scanf("%d %d",&x[i],&y[i]);        
            int cnt = 0;
            for(int i=0;i<n;++i)
                    for(int j=i+1;j<n;++j)
                            P[cnt++] = p(i,j);
            sort(P,P+cnt);
            cnt = unique(P,P+cnt)-P;
            printf("%d\n",cnt);
            return 0;
    }
     
    /**************************************************************
        Problem: 1533
        User: 311709001223
        Language: C++
        Result: 正确
        Time:4 ms
        Memory:2040 kb
    ****************************************************************/

# [Problem I 小L的长方形][Problem I _L] #

这题傻逼

// #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define lp rt<<1
    #define rp rt<<1|1
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    using namespace std;
     
    typedef long long ll;
    typedef pair<int ,int> P;
     
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e6+7;
     
     
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            // ios::sync_with_stdio(0);
            // cin.tie(0);
            int a;
            scanf("%d",&a);
            if(a%8==0) {
        
                    int h,l,area;
                    h = a/8;
                    l = h*3;
                    area = h*l;
                    printf("%d %d %d\n",l,h,area);
            }
            else {
        
                    double h,l,area;
                    h = 1.0*a/8.0;
                    l = h*3.0;
                    area = h*l;
                    printf("%.3lf %.3lf %.3lf\n",l,h,area);
            }
            return 0;
    }
     
    /**************************************************************
        Problem: 1534
        User: 311709001223
        Language: C++
        Result: 正确
        Time:2 ms
        Memory:1648 kb
    ****************************************************************/

[Problem A _L]: http://acm.zzuli.edu.cn/problem.php?id=1526
[Problem B _L]: http://acm.zzuli.edu.cn/problem.php?id=1527
[Problem C _L]: http://acm.zzuli.edu.cn/problem.php?id=2041
[Problem D _L]: http://acm.zzuli.edu.cn/problem.php?id=1528
[Problem E _L]: http://acm.zzuli.edu.cn/problem.php?id=1530
[Problem F _L]: http://acm.zzuli.edu.cn/problem.php?id=1531
[Problem G _L]: http://acm.zzuli.edu.cn/problem.php?id=1532
[Problem H _L]: http://acm.zzuli.edu.cn/problem.php?id=1533
[Problem I _L]: http://acm.zzuli.edu.cn/problem.php?id=1534