三道签到题,后面两道也不难,网速感人,被手速狗惨虐.

A

模拟即可,直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

int mp[255];

int main()
{
int n;
scanf("%d%*c",&n);
int m=2*n-2,ans=0;
memset(mp,0,sizeof(mp));
for(int i=1;i<=m;++i)
if(i&1) mp[getchar()]++;
else {
char c=getchar()+32;
if(mp[c]) --mp[c];
else ++ans;
}
printf("%d\n",ans);
return 0;
}

B

字符串s(下标从1开始)逆序操作,对于输入位置$a_i$,一直到$|s|-a_i+1$ ,进行逆序.
其实对于相同位置,做偶数次操作等于0次,奇数次等于1次,第一遍先筛除重复的(^(异或)即可)
然后从左至右依次交换,一直到下一个交换的位置,若上一次进行逆序操作,则这次抵消,直至下一个位置不再抵消

  • 这题直接模拟肯定TLE,但是我LOCK之后发现房间里的TLE写法都被另一个人X了,WTF…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;

const int maxn=2*100*100*10 + 10;
char s[maxn];
bool pos[maxn];

int main()
{
scanf("%s",s+1);
int l=strlen(s+1);
int n,t;
scanf("%d",&n);
memset(pos,0,sizeof(pos));
for(int i=0;i<n;++i){
scanf("%d",&t);
pos[t]^=1;
}
int yes=0;
for(int i=1;i<=l/2;++i)
if(pos[i]){
if(!yes) swap(s[i],s[l-i+1]);
yes^=1;
}
else if(yes)
swap(s[i],s[l-i+1]);
printf("%s\n",s+1);
return 0;
}

C

这题也是模拟,…甚至比B还水,排序后从后向前找符合条件的长度对即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

const int maxn=100000 + 10;
typedef long long ll;
int a[maxn];
ll res[maxn];

int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",&a[i]);
sort(a,a+n);
int i,cnt=0;
memset(res,0,sizeof(res));
for(i=n-1;i>0;--i){
if(a[i]==a[i-1] || a[i]==a[i-1]+1){
res[cnt++]=a[i-1];
--i;
}
}
ll ans=0;
for(int i=0;i<cnt;i+=2) ans+=res[i]*res[i+1];
cout<<ans<<endl;
return 0;
}

D

刚开始想复杂了,看了别人的代码豁然开朗,这题其实很简单
DFS:每次检查当前以当前块为左上角的正方形的墙的个数,若为1则必定变为空地,接着再对它一圈的点进行dfs(填为空地后影响了以其一周的点为左上角的正方形的墙的个数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;

const int maxn=2000 + 10;
int pic[maxn][maxn];
int n,m;

bool inside(int x,int y)
{
return x>=0 && x<n && y>=0 && y<m;
}

void change(int x,int y)
{
if(!inside(x,y)) return;
int cnt=0;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
cnt+=(pic[x+i][y+j]==0);
if(cnt==1){
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
pic[x+i][y+j]=1;
for(int i=-1;i<2;++i)
for(int j=-1;j<2;++j)
change(x+i,y+j);
}
}

int main()
{
scanf("%d %d",&n,&m);
getchar();
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
char c=getchar();
pic[i][j]=(c=='*')?0:1;
}
getchar();
}
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
change(i,j);
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)
printf(pic[i][j]?".":"*");
puts("");
}
return 0;
}

E

典型的中途相遇,用到了二进制枚举子集,比较经典了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;

#define min(a,b) ((a)<(b))?(a):(b)

typedef unsigned long long ll;
const ll fac[]={
0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000
};
const ll INF=2e16;

map<ll,ll> has1[30];
map<ll,ll> has2[30];
map<ll,ll>::iterator it;
vector<int> a;
int n,k;
ll s;

int main()
{
//freopen("test.txt","r",stdin);
cin>>n>>k>>s;
for(int i=0;i<n;++i){
int t;
scanf("%d",&t);
if(t<=s) a.push_back(t);
}
for(int i=0;i<30;++i){
has1[i].clear();
has2[i].clear();
}
int m=a.size();
int p1=m/2,p2=m-p1;
int m1=1<<p1,m2=1<<p2;

for(int bit=0;bit<m1;++bit)
for(int tbit=bit;;tbit=(tbit-1)&bit){
ll sum=0,tot=0;
for(int i=0;i<p1;++i)
if(bit&(1<<i)){
if(tbit&(1<<i)){
++tot;
if(a[i]<20) sum+=fac[a[i]];
else sum+=INF;
}else sum+=a[i];
}
if(sum<=s) has1[tot][sum]++;
if(!tbit) break;
}

for(int bit=0;bit<m2;++bit)
for(int tbit=bit;;tbit=(tbit-1)&bit){
ll sum=0,tot=0;
for(int i=0;i<p2;++i)
if(bit&(1<<i)){
if(tbit&(1<<i)){
++tot;
if(a[i+p1]<20) sum+=fac[a[i+p1]];
else sum+=INF;
}else sum+=a[i+p1];
}
if(sum<=s) has2[tot][sum]++;
if(!tbit) break;
}

ll ans=0;
for(int i=0;i<=k;++i)
for(it=has2[i].begin();it!=has2[i].end();++it){
for(int t=0;t+i<=k;++t)
if(s>=(it->first))
ans+= it->second*has1[t][s-(it->first)];
}
cout<<ans<<endl;
return 0;
}