比赛链接

A

思路:对于每个字符看它是否被使用过,初次使用进行标记,再次使用的时候看与上一个字符是否相等即可。

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

#include<bits/stdc++.h>
using namespace std;
bool tong [30];
int main()
{
int _;
for(cin>>_;_;_--)
{
memset(tong,0,sizeof(tong));
bool f=1;//会怀疑
string s;
int n;
cin>>n;
cin>>s;
//int n= s.length();
tong[s[0]-'A']=1;
for(int i=1;i<n;i++)
{
if(s[i]==s[i-1])
{
continue;
}
else
{
if(tong [s[i]-'A'])
{
f=0;
}
else
{
tong[s[i]-'A']=1;
}
}
}
if(f)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}


}

B

思路:对于1~9,每次都添加一位,判断是否超过n,超过换下一个数从1位开始,不超过再次增加一位。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m;
ll cal(ll n)
{
ll res=n;
ll te=0;
while(res<=m)
{

te++;
res*=10;
res+=n;
//cout<<res <<" \t "<<m <<"\t"<<te<<endl;
}
//cout<<"te"<<te<<endl;
return te;
}
int main()
{
ll _;
ll ans=0;

for(cin>>_;_;_--)
{
cin>>m;
ans=0;
for(ll i=1;i<=9;i++)
{
ans+=cal(i);
//cout<<ans<<endl<<endl;
}
cout<<ans<<endl;
}


}

C

思路:等间距的所有数从左上角开始放,不难发现最佳间距就是n-2(这个间距指的是两个相邻数之间的数字数量)。同时发现n=2是无解的。

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
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int main()
{
int _;

int n;

for(cin>>_;_;_--)
{
memset(a,0,sizeof(a));
cin>>n;
if(n==1)
{
cout<<1<<endl;
continue;
}
if(n==2)
{
cout<<-1<<endl;
continue;
}
int now=1;
int delta=n-1;
for(int i=1;i<=n*n;i++)
{
int hang = int (ceil(double(now)/n));
int lie = now%n;
//cout<<now <<" "<<i<<endl;
if(lie==0)
{
lie=n;
}
a[hang][lie]=i;
now+=delta;
now%=n*n;
if(now==0)
{
now=n*n;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}


}

D

思路:对等式进行变形得到a_{i}-i = a_{j}-j ,记录a_{i}-i的数量,通过组合数计算它的贡献,对贡献进行求和。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll ,ll > MP;
ll _,n,m;
ll a[200005];
long long ans=0;
set<ll > st;
int main()
{
for(cin>>_;_;_--)
{
cin>>n;
ans=0;
MP.clear();
st.clear();
for(ll i=1;i<=n;i++)
{
cin>>a[i];
MP[a[i]-i]++;
st.insert(a[i]-i);
}
set<ll > ::iterator stt;
for(stt=st.begin();stt!=st.end();stt++)
{

ans+=MP[*stt]*(MP[*stt]-1)/2;
//cout<<ans<<endl;
}
cout<<ans<<endl;
}
}

E

思路:维护两个数组pre和suf表示左侧最右边和右侧最左边的 * 号占据位置i时需要花费的代价,对每个位置考虑左边占据和右遍占据两种情况,取所有情况的最小值。
小心数据规模变大带来的初始化超时问题

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
//team lots of balloons
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e6+7;
const double pi=acos(-1);
using namespace std;
int _,n,m,x;
char s[maxn];
ll pre[maxn];
ll suf[maxn];
ll mi=mod*mod;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
for(cin>>_;_;_--)
{
mi=mod*mod;
x=0;
cin>>n;
cin>>s+1;

for(int i=1;i<=n;i++)
{
//pre[i]=0;
if(s[i]=='.')
{
pre[i]=x;
}
else
{
x++;
}
pre[i]+=pre[i-1];
}
x=0;
for(int i=n;i>=1;i--)
{
//suf[i]=0;
if(s[i]=='.')
{
suf[i]=x;
}
else
{
x++;
}
suf[i]+=suf[i+1];
}

for(int i=1;i<=n;i++)
{
//左边占据
mi=min(mi,pre[i]+suf[i+1]);
//右边占据
mi=min(mi,pre[i-1]+suf[i]);
}
cout<<mi<<endl;
memset(pre,0,8*n+24);
memset(suf,0,8*n+24);
}
return 0;
}

F1

思路:二分

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
//team lots of balloons
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int _,n,m,a;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.in","r",stdin);
//freopen("mine.out","w",stdout);
int have=0;
cin>>n>>m;
cin>>m;
int l=1;
int r=n;
int mid;
while(l<r)
{
mid=(l+r)>>1;
cout<<"? "<<l<<" "<<mid<<endl;
cout.flush();
cin>>a;
//cout<<have+(mid-l+1-a)<<"\t"<<m<<endl;
if(have+(mid-l+1-a)>=m)
{
r=mid;
}
else
{
have+=(mid-l+1-a);
l=mid+1;

}
}
cout<<"! "<<l<<endl;
return 0;
}

写在最后:
被大佬上了一课,以后看到两边都是相同数据格式的式子先进行移项,把下标相同的放到一边。