A题
题目大意：
给你一个字符串，奇数的时候是钥匙，偶数的时候是门，一把钥匙只能开对应的门，然后问你最少额外需要多少把钥匙。
分析：
用的数组记录一下就行，（注意的是先开门，再拿钥匙！开始错在这里了，决心好好学英语）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int main()
{
int n,vist[];
char a[];
scanf("%d",&n);
scanf("%s",a);
memset(vist,,sizeof(vist));
vist[a[]-'a']=;
int sum=;
int i;
for( i=;i<*n-;i=i+)
{
if(vist[a[i]-'A']==)
{
sum++;
}
else
{
vist[a[i]-'A']--;
}
vist[a[i+]-'a']++;
}
printf("%d\n",sum);
return ;
}
B题
题目大意
一个字符串str ,从1 开始长度为s，每次给你一个 a[i] ，然后将 [ a[i] , (s-a[i]+1) ] 翻转，问你经过n次操作以后整个字符串是什么样的。
分析
需要从内到外，看那些区域需要翻转，那些区域不需要就行了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
#define maxn 410004
using namespace std;
int vist[maxn],zhuan[maxn]; int main()
{
char a[];
int n,num;
scanf("%s",a);
int len=strlen(a);
memset(vist,,sizeof(vist));
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&num);
vist[--num]++; }
int sum=;
for(int i=;i<len/;i++)
{
sum+=vist[i];
if(sum%)
swap(a[i],a[len-i-]);
}
printf("%s\n",a);
return ;
}
C题
题目大意
给出n条线段的长度，任意一条长度为len的线段可以当作len或len-1的线段使用，求能构成的矩形的最大的总面积（可以是多个矩形的和）。
分析
要是总面积最大，就要贪心，使长度最大的对子和长度次最大的对子组合，可以是多个矩形的和。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define INF 10000000
using namespace std;
int main()
{
int n;
long long a[];
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%I64d",&a[i]);
sort(a+,a++n);
long long flag=;
long long ans =;
for(int i=n;i>;)
{
if(a[i]==a[i-]||a[i]-==a[i-])
{
if(flag)
{
ans+=flag*a[i-];
flag=;
}
else
flag=a[i-];
i=i-;
}
else
i--;
} printf("%I64d\n",ans);
return ;
}
D题
题目大意
给你一个n*m的格子,'.'代表空地,'*'代表墙,你使墙变为空地,问你最小的次数使每个空地块为矩形。
分析
每当搜索到有3个'.'的就让那个余下的变为空地,再次在它的四周8格以每4格搜索,直到都符合。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std; char a[][];
int n, m; bool check(int x, int y)
{
if(a[x][y] == '.' || x < || y < || x > n || y > m) return ; if(a[x][y - ] == '.' && a[x - ][y - ] == '.' && a[x - ][y] == '.') return ;
if(a[x][y + ] == '.' && a[x - ][y + ] == '.' && a[x - ][y] == '.') return ;
if(a[x][y - ] == '.' && a[x + ][y - ] == '.' && a[x + ][y] == '.') return ;
if(a[x][y + ] == '.' && a[x + ][y + ] == '.' && a[x + ][y] == '.') return ; return ;
}
int x[]= {-,-,,,,,,-};
int y[]= {,,,,,-,-,-};
int main()
{
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++)
{
scanf("%s", a[i] + );
} queue<pair<int , int> > q;
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
if(check(i, j))
q.push(make_pair(i, j));
}
} while(!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
if(!check(i, j)) continue;
a[i][j] = '.';
for(int ii=; ii<; ii++)
{
if( check(i + x[ii], j + y[ii]))
{
q.push(make_pair(i + x[ii], j + y[ii]));
}
}
} for(int i = ; i <= n; i++)
{
printf("%s\n", a[i] + );
} return ;
}