A：Course
B：Sample Game
C：LCS
题意：已知三个字符串长度，和他们两两之间的LCS长度a,b,c，输出满足条件的三个字符串。
思路：构造题。min({a,b,c})肯定是他们两两之间共有的一个前缀，所以给三个字符串加上这么多个'a'后，然后以此根据a，b，c剩下的值去填'b'和'c'，全填完后如果有一个字符串的长度大于n，则输出-1。否则继续填字符d或者e或f直至字符串长度等于n。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,n; cin >> a >> b >> c >> n;
string s1,s2,s3;
int minn=min(a,min(b,c));
a-=minn,b-=minn,c-=minn;
for(int i=1;i<=minn;i++) {
s1+='a';
s2+='a';
s3+='a';
}
if(a>=b&&a>=c) {
for(int i=1;i<=a;i++) {
s2+='b';
s1+='b';
}
if(b==0)
for(int i=1;i<=c;i++) {
s1+='c';
s3+='c';
}
else if(c==0) {
for(int i=1;i<=b;i++) {
s3+='c';s2+='c';
}
}
}
else if(b>=a&&b>=c) {
for(int i=1;i<=b;i++) {
s2+='b';
s3+='b';
}
if(a==0)
for(int i=1;i<=c;i++) {
s1+='c';
s3+='c';
}
else if(c==0) {
for(int i=1;i<=a;i++) {
s1+='c';s2+='c';
}
}
}
else if(c>=a&&c>=b) {
for(int i=1;i<=c;i++) {
s3+='b';
s1+='b';
}
if(b==0)
for(int i=1;i<=a;i++) {
s1+='c';
s2+='c';
}
else if(a==0) {
for(int i=1;i<=b;i++) {
s3+='c';s2+='c';
}
}
}
int len1=s1.length(),len2=s2.length(),len3=s3.length();
if(len1>n||len2>n||len3>n) {
cout << "NO" << endl;
return 0;
}
if(len1<n) {
for(int i=1;i<=n-len1;i++) s1+='d';
}
if(len2<n) {
for(int i=1;i<=n-len2;i++) s2+='e';
}
if(len3<n) {
for(int i=1;i<=n-len3;i++) s3+='f';
}
cout << s1 << endl << s2 << endl << s3 << endl;
return 0;
} D：Rebuild Tree
E：Tree Xor
F：Just a joke
题意：有n个点的无向图，两个人每次可以选择进行一种操作；1.删掉一条边；2.删掉一个没有环的连通分量。 问最后谁赢。
思路：第一种操作边数-1，第二种操作点数-k且边数-(k-1)。所以每次不管进行那种操作边和点的个数都会减少一个奇数，所以判断一下n+m的奇偶性即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m; cin >> n >> m;
for(int i=1;i<=n;i++) {
int u,v; cin >> u >> v;
}
if((m+n)%2==0) {
cout << "Bob" << endl;
}
else cout << "Alice" << endl;
return 0;
}G：Product
H：Convolution
I：Inverse Pair
题意：给你一个序列a,现在你可以对a序列每个数+1或+0使它变成一个新序列b，序列ci=bi+ai。输出序列c的逆序对数。
思路：首先求出序列a中的逆序对数，然后记录下每个ai加1是否之前已经出现过了，统计这样的ai的个数。因为如果存在，我们令它加1，就减少了一个逆序对的数量。最后二者做差即可。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
ll b[N];
struct node{
ll val;
ll pos;
}a[N];
ll tree[N], c[N];
ll sum, n;
int cmp(node a, node b) {
return a.val < b.val;
}
void add(int m, int k) {
while (m <= n) {
tree[m] += k;
m += m & -m;
}
}
ll inquiry(ll n) {
ll sum = 0;
while (n) {
sum += tree[n];
n -= n & -n;
}
return sum;
}
int main() {
cin >> n;
sum = 0;
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= n; i++) {
cin >> a[i].val;
a[i].pos = i;
}
ll tmp=0;
for(int i=1;i<=n;i++) {
if(b[a[i].val+1]) tmp++;
else b[a[i].val]=1;
}
for (int i = 1; i <= n; i++) {
}
sort(a + 1, a + 1 + n, cmp);
ll cnt = 1;
for (int i = 1; i <= n; i++) {
if (i != 1 && a[i].val != a[i - 1].val) cnt++;
c[a[i].pos] = cnt;
}
for (int i = 1; i <= n; i++) {
add(c[i], 1);
sum += (i - inquiry(c[i]));
}
cout << sum - tmp << endl;
}J：Average
题意：给你两个序列a和b，矩阵，让你在矩阵w中找一个子矩阵，其中子矩阵的长不得小于x，宽不得小于y且子矩阵的平均值最大。输出该平均值
思路：由题意我们可以写出平均值的式子，又因为w[i][j]=a[i]+b[j],所以子矩阵的和为：
，联立上面两个式子可得平均值最简式为：
。
所以这道题就变成了去求a的长度至少为x的子区间的最大平均值和b的长度至少为y的最大平均值相加即可，poj2018裸题,二分平均数为mid，把原数组中每个数都减去mid，若最大和>0,就是平均数取小了。这就涉及到均值比较的技巧：平均值大小的比较,可以转换为每对对应元素差值之和与0的比较。。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
double a[100005],b[100005],sum[100005];
double aa[100005],bb[100005],ssum[100005];
int main(){
int n,m,x,y;
cin>>n >> m>>x>>y;
for(int i=0;i<n;i++) scanf("%lf",&a[i]);
for(int i=0;i<m;i++) scanf("%lf",&aa[i]);
double eps=1e-6;
double l1=-1e6,r1=1e6;
while(r1-l1>eps){
double mid=(r1+l1)/2;
for(int i=0;i<n;i++) b[i]=a[i]-mid;
for(int i=0;i<n;i++) sum[i]=sum[i-1]+b[i];
double ans=-1e10,minval=1e10;
for(int i=x-1;i<n;i++){
minval=min(minval,sum[i-x]);
ans=max(ans,sum[i]-minval);
}
if(ans>0) l1=mid; else r1=mid;
}
double l2=-1e6,r2=1e6;
while(r2-l2>eps){
double mid=(r2+l2)/2;
for(int i=0;i<m;i++) bb[i]=aa[i]-mid;
for(int i=0;i<m;i++) ssum[i]=ssum[i-1]+bb[i];
double ans=-1e10,minval=1e10;
for(int i=y-1;i<m;i++){
minval=min(minval,ssum[i-y]);
ans=max(ans,ssum[i]-minval);
}
if(ans>0) l2=mid; else r2=mid;
}
printf("%.10lf\n",r1+r2);
return 0;
}
京公网安备 11010502036488号