题意
给出n和n个数，判断该数列是否是凸形的。
解题思路
从前往后第一对逆序数，和从后往前第一队逆序数，如果都非零而且相邻，证明该数组是凸形的。
代码
#include <cstdio>
const int maxn = + ;
int a[maxn]; int main()
{
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
int q = , h = , i;
for(i = ; i < n - ; i++) {
if(a[i] < a[i + ])
q++;
else
break;
}
for(; i < n - ; i++) {
if(a[i] > a[i + ])
h++;
else
break;
}
//printf("%d %d\n", q, h); if(q && h && q + h == n - )
puts("Yes");
else
puts("No");
}
return ;
}
题意
给出n，然后给出两个长度为n的序列S 和 D，问给每个D加上一个数k（可正，可负，可零），最大的耦合度是多少
解题思路
先用S减D得到每个差值的次数，然后找到差值次数最多的数即可。
代码
#include <cstdio>
#include <map> using namespace std;
const int maxn = + ;
int D[maxn], S[maxn];
int n; map<int, int> mp;
int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%d", &D[i]);
}
for(int i = ; i < n; i++) {
scanf("%d", &S[i]);
} mp.clear();
for(int i = ; i < n; i++) {
mp[S[i] - D[i]]++;
}
int maxc = ;
map<int, int>::iterator it;
for(it = mp.begin(); it != mp.end(); it++) {
if((*it).second > maxc)
maxc = (*it).second;
}
printf("%d\n", maxc);
}
return ;
}
给出n和k，然后n个数，只要有一个数加上k能够将7整除，就是Yes。
#include <cstdio> int n, k;
int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
int a, f = ;
for(int i = ; i < n; i++) {
scanf("%d", &a);
if((a + k) % == )
f = ;
}
if(f)
puts("Yes");
else
puts("No");
}
return ;
}
ZOJ 4035 Doki Doki Literature Club
给出n个单词列表和单词限制数m，然后每个单词的满足度，问组成m个最大满意度的单词列表。
排序，注意先按满意度排，再按照字典序排，另外可能超int范围。
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int wl = + ;
const int maxw = + ;
struct Word {
char w[wl];
int s;
bool operator < (const struct Word &a) const {
if(a.s == s) {
if(strcmp(a.w, w) > )
return ;
else
return ;
}
return a.s < s;
}
}wo[maxw]; int n, m;
int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%s %d", wo[i].w, &wo[i].s);
} sort(wo + , wo + n + );
/*for(int i = 1; i <= n; i++) {
printf("%s %d\n", wo[i].w, wo[i].s);
}*/
long long sc = ;
for(int i = ; i <= m; i++) {
sc += (long long)(m - i + ) * wo[i].s;
}
printf("%lld",sc);
for(int i = ; i <= m; i++) {
printf(" %s", wo[i].w);
}
puts("");
}
return ;
}