x3268在这么下去不行啊…… 数据结构依赖症需要改正了，明明数组简单粗暴而且不容易错，我非要用优先队列到底是为了什么……（C再次被Fst，哭）
这个就想象成游戏的时候的钥匙寄存数组就好，发现钥匙则 record[钥匙]++,遇到门的时候如果有钥匙就record[钥匙]--，没有钥匙就说明初始的时候需要带着这个钥匙，则ans++，遍历完了之后输出ans即可。
Code：
#include <map>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
bool cmp(const int a, const int b)
{
return a > b;
}
map<char,int> mci;
int main()
{
mci.clear();
int n,ans=0; cin>>n;
string s;cin>>s;
for(int i=0;i<s.length();i++)
{
if(islower(s[i])) mci[s[i]]++;
if(isupper(s[i]))
{
if(mci[tolower(s[i])]==0) ans++;
else mci[tolower(s[i])]--;
}
//cout<<i<<":"<<ans<<endl;
}
cout<<ans;
return 0;
}
有一个字符串，在m天的时间内，这位同学每天都会选择一个位置a，然后把从左边数第a个和右边数第a个字符以及他们中间的字符组成的字符串反转顺序，问这m天过去之后字符串是什么样子的。
我们要知道，每个字符只有2种可能，原字符，或者和他对称的右边那个字符，因为无论怎么颠倒，每个字符也不会在这两种位置以外的地方。那么我们用一个数组来标记这个字符是否在原位，那有人问了，难道用线段树维护，区间加一减一么？不好意思，本人的线段树也不熟呢，话说你会的话求教我一下呢哈哈哈~这里的话我们记忆的仅仅只是每个位置被a挑中的奇偶性，因为奇数次相当于颠倒1次，偶数次等于没做事嘛。For example，如果现在第i位的字符，被选中偶数次，那么对于它来说，他和他前面的那个字符是一样的情况，前面那个字符i-1位如果是交换状态，那么这个第i位也应该是处于要交换的状态，反之，我相当于颠倒了一次，那么是否交换应该和前一个的情况相反。
这个想清楚了的话那就简单的多啦~
Code:
#include <cmath>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
bool cmp(const int a, const int b)
{
return a > b;
}
int main()
{
string s;
int m=0,now=0,a[100086]={0},b[200086]={0};
cin>>s>>m;
int len=s.length();
for(int i=0;i<m;i++)
{
scanf("%d",&now);
a[now-1]=1-a[now-1];
}
int rev=0;
for(int i=0;i<len/2;i++)
{
if(a[i]!=0) rev=1-rev;
b[i]=b[len-i-1]=rev;
}
for(int i=0;i<len;i++)
{
if(b[i]==1) printf("%c",s[len-i-1]);
else printf("%c",s[i]);
}
return 0;
}
有一堆棍子，对于每个棍子，我们有“使用原长度”和“使用原长度减一”两种选择，问组成的矩形总面积的最大值。
我们从平方差公式知道，距离越小的长宽之积越大，一边长一定的时候，面积与另一边长成正比增加。
那么就简单了，排序之后从大到小找可以做对边的两根棍子做长边，再找一对做短边，乘积加进ans里，然后再找长边……如此循环重复，O(n)结束战斗
Code：
#include <cmath>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
int n=0, ct=0, a[100086]={0}, b[100086]={0};
int main()
{
cin>>n;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=n; i>=0; i-=2)
{
if(a[i] == a[i-1]) b[ct++]=a[i];
else
{
if(a[i]-a[i-1] == 1) b[ct++]=a[i-1];
else ++i;
}
}
ll ans=0;
for(int i=0;i<=ct-1;i+=2) ans+=(ll)b[i]*b[i+1];
cout<<ans;
return 0;
}
有一张图，星号是墙，点号是空地，要求推倒最少数量的墙，令所有的房间都是矩形。
简单的说，如果发现L形，那么那个阻碍成为矩形的墙就需要被消灭掉,然后接着看会造成的其他的影响一个个磨消掉，直到达成最终要求即可。
Code：
#include <bits/stdc++.h>
//Code By cikofte@Codeforces
#include <cmath>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#definest first
#definend second
#definemp make_pair
#definepb push_back
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#definectrl( xx,yy )( xx>=1 and yy>=1 and xx<=m and yy<=n and s[xx][yy]=='.' )
using namespace std;
intm,n;
chars[3000][3000];
charh[3000][3000];
intbozuk( int x,int y )//Bad mood .Turkey
{
if( s[x][y]!='*' )return0;
if( ctrl( x-1,y ) and ctrl( x-1,y+1 ) and ctrl( x,y+1 ) )return1;
if( ctrl( x,y+1 ) and ctrl( x+1,y+1 ) and ctrl( x+1,y ) )return1;
if( ctrl( x+1,y ) and ctrl( x+1,y-1 ) and ctrl( x,y-1 ) )return1;
if( ctrl( x,y-1 ) and ctrl( x-1,y-1 ) and ctrl( x-1,y ) )return1;
return0;
}
int main()
{
cin>>m>>n;
for(ll i=1;i<=m;i++)scanf("%s",s[i]+1);
queue< pair<int,int> >Q;
for(ll i=1;i<=m;i++)
for(ll j=1;j<=n;j++)
if( bozuk( i,j ) )Q.push( mp(i,j) ), h[i][j]=1;
intx,y,xx,yy;
while( Q.size() )
{
x = Q.front().st;
y = Q.front().nd;
Q.pop();
s[x][y] = '.';
h[x][y] = 0;
for(ll i=-1;i<=1;i++)
for(ll j=-1;j<=1;j++)
{
if( !i and !j )continue;
xx = x+i;
yy = y+j;
if( xx<1 or xx>m or yy<1 or yy>n
or h[xx][yy] or !bozuk( xx,yy ) )continue;
Q.push( mp(xx,yy) ), h[xx][yy] = 1;
s[xx][yy] = '.';
}
}
for(ll i=1;i<=m;i++) printf("%s\n",s[i]+1);
return 0;
}