[数据结构与算法]The 14th Jilin Provincial Collegiate Programming Contest

题目链接：The 14th Jilin Provincial Collegiate Programming Contest?

question：
Problem A. Chord

thought：
其实很简单，但是没有想仔细，要注意一些细节?

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

inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
const int N = 1e5+7;
string s[20]={"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};
void solve(){
	string a,b,c;
	cin>>a>>b>>c;
	int id1,id2,id3;
	for(int i = 0; i <= 11; i ++)
	if(s[i]==a) id1=i;
	
	for(int i = 0; i <= 11; i ++) 
	if(s[i]==b) id2=i;
	
	for(int i = 0; i <= 11; i ++)
	if(s[i]==c) id3=i;
	
	
	if((id2-id1+12)%12==4&&(id3-id2+12)%12==3) 
	puts("Major triad");
	else if((id2-id1+12)%12==3&&(id3-id2+12)%12==4)
	puts("Minor triad");
	else puts("Dissonance");
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

question:

Problem C. String Game

找字符串中是否出现另一个字符串，计算出现了几次

thought：

动态规划?

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
int dp[N];
int main() {
	string a, b;
	while (cin >> a >> b) {
		memset(dp, 0, sizeof dp);
		int lena = a.size();
		int lenb = b.size();
		dp[0] = 1;
		for(int i = 0; i < lena; i ++ ) {
			for (int j = lenb; j >= 1; j -- ) {
				if (a[i] == b[j - 1]) {
					dp[j] += dp[j - 1];
					dp[j] %= mod;
				}
			}
		}
		cout << dp[lenb] << endl;
	}
	return 0;
}

?question：

Problem E. Shorten the Array

改变数组的长度然后输出最短长度

thought：

先找出数组中的最小元素，然后遍历数组看是否存在一个不是x的倍数的数，如果存在就代表存在 y 满足 gcd( x , y ) ≠ x.那么答案就是 1。

如果不存在，那么答案就是 num(x) / 2 (向上取整)。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main(){
	int t;
	scanf("%d", &t);
	while (t -- ) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++ ) scanf("%d", a + i);
		int mi = a[1];
		for (int i = 1; i <= n; i ++ ) mi = min(mi, a[i]);
		int f = 0, cnt = 0;
		for (int i = 1; i <= n; i ++ ) {
			if (a[i] == mi) cnt ++;
			if (a[i] % mi) f = 1;
		}
		if (f) cout << 1 << endl;
		else cout << (cnt + 1) / 2 << endl;
	}
	return 0;	
}