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 */