The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored(E F G H I)

http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=392

E:Sequence in the Pocket

思路:从后往前判断在不在应该在的位置,如果不在则需要放到最前面,通过cnt控制当前的数 比较 排好序的数组的数。

code:

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
#define INF 2000000000
#define eps 1e-8
#define pi  3.141592653589793
int a[100001],b[100001];
int main()
{
    int t;scanf("%d",&t);
    while(t--) {
        int n ,cnt = 0;scanf("%d",&n);
        for(int i = 0; i < n; i++) {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        sort(b,b+n);
        for(int i = n-1; i >= 0; i--) {
            if(a[i] != b[i+cnt]) cnt++;
        }
        printf("%d\n",cnt);
    }
 }

F:Abbreviation

思路:无

code:

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
#define INF 2000000000
int main(){
    LL n;cin>>n; 
    while(n--){
        string s,ans="";
        cin>>s;
        for(int i = 0 ; i < s.size() ; i++){
            if(i == 0){
                ans += s[i];
            }else{
                if(s[i] != 'a' && s[i] != 'e' && s[i] != 'o'&& s[i] != 'i'&& s[i] != 'y'&& s[i] != 'u'){
                    ans += s[i];
                }
            }    
        }
        cout<<ans<<endl; 
    }
    return 0;
}
/*
5
subconscious
oipotato
word
symbol
apple
*/

G:Lucky 7 in the Pocket

思路:

记当前这个数为n,则(n/7+(n%7==0)?0:1)*7 ,则表示大于等于这个数切能被7整除的数。

再判断一下是不是4的倍数就行了,如果是则答案是(n/7+(n%7==0)?1:2)*7 

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
#define INF 2000000000
int main(){
    LL n;cin>>n; 
    while(n--){
        LL m;cin>>m;
        LL k = m/7 + (m%7==0?0:1);
        cout<<(((k*7LL)%4)==0?((k+1LL)*7LL):(k*7LL))<<endl; 
    }
    return 0;
}
/*
7
1235
20
28
*/

H:Singing Everywhere

思路:各种判断

情况分为2种

1、如果有1 3 2 3 1这种,考虑删除两个峰值之间的这个2

2、考虑删除峰值

反正对答案影响肯定是-0,-1,-2。三种情况,大力推就行

code:

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
#define INF 2000000000
#define eps 1e-8
#define pi  3.141592653589793
int a[100001];
int cnt[100001];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        memset(cnt,0,sizeof(cnt));
        scanf("%d",&n);
        for(int i = 0 ; i < n ; i++){
            scanf("%d",&a[i]);
        }
        if(n == 1 ||n == 2){
            puts("0");
        } // n==1 or n==2 不用做操作的 
        else{
            int sum = 0,f = 0,f1 = 0;
            if(a[1] < a[0]) cnt[1]++;
            if(a[n-2] < a[n-1]) cnt[n-2]++;
            //考虑到可能可以删除  1 or n-1 
            for(int i = 1 ; i < n-1 ; i++){
                if(a[i]>a[i-1] && a[i]>a[i+1]){
                    sum++;
                    if((a[i-1] < a[i+1] && (i+1==n ||a[i+1] <= a[i+2]) )|| a[i-1]==a[i+1] ){
                        f1 = 1;
                    }//删除峰值 
                    cnt[i-1]++;
                    cnt[i+1]++;
                }
            }
            //cnt增加峰值旁边的两个数,考虑情况1 
            for(int i = 1 ; i < n-1 ; i++){
                if(cnt[i] == 2){
                    if(a[i-1] == a[i+1]){
                        f = max(f,2);
                    }
                    else if(a[i-1] < a[i+1]){
                        f = max(f,1);
                    }
                    else if(a[i-1] > a[i+1]){
                        if((i-1==0) || a[i-2]>=a[i-1]){
                            f = max(f,1);    
                        }
                    }
                }
            }
            if(f){
                printf("%d\n",sum-f);continue;
            }
            printf("%d\n",sum-f1);
        }
    }
}
/*
5
6
1 1 4 5 1 4
6
1 1 4 7 5 5
6
1 1 4 7 5 4
7
3 1 5 4 5 1 7
7
1 2 3 4 5 1 7

2
2
1 2
7
1 3 3 3 3 3 1
*/

I:Fibonacci in the Pocket

思路:

斐波那契数列 写一下前几项就知道是 奇奇偶 奇奇偶 奇奇偶 奇奇偶....

循环节是3。

另外一个性质是,一个数%3,等于这个数各个位数的和%3

既然是求和

考虑起点和终点吧,起点为a 终点为b,利用性质可以很方便算出a%3 和 b%3的值

那么就知道了,起点位于循环节的第几个,终点位于循环节的第几个。

分类讨论一下就知道和是奇数还是偶数。

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
#define INF 2000000000
#define eps 1e-8
#define pi  3.141592653589793
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        string a,b;
        cin>>a>>b;
        int s1 = 0,s2 = 0;
        for(int i = 0 ; i < a.size() ; i ++){
            s1+=(a[i]-'0');s1%=3; 
        }
        for(int i = 0 ; i < b.size() ; i ++){
            s2+=(b[i]-'0');s2%=3; 
        }
        if((s1+s2)%3==0 || s1==0 && s2==2 || s1==1&&s2==0){
            puts("0");
        }//都位于循环节末尾或者起点在0 终点在2  或者起点在1终点在0
        else{
            puts("1");
        }
    }
}
/*
6
1 2
1 3
1 4
1 5
123456 12345678987654321
123 20190427201904272019042720190427
*/

 

上一篇:Spring事务失效的 8 大原因,这次可以吊打面试官了!


下一篇:聊聊spring事务失效的12种场景,太坑了