T1
直接按照题目要求模拟，复杂度$O(M+N)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NR=1005;
int n,m;
int a[NR],b[NR];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
for(int i=1;i<=m;i++)scanf("%d",b+i);
int j=1;
for(int i=1;(j<=n)&&(i<=n);i++)
if(a[i]<=b[j])j++;
printf("%d",j-1);
return 0;
}
|
T2
将这个字符串以2为界分为几部分
$$（部分1）2（部分二）2\cdots2（部分n）$$题目所等效的条件为：
在这个字符串中，2是固定的，1可以随意移动，0可以在其所在的部分任意移动。
所以简单的贪心一下，把每个部分的0移到这个部分的最前头，把每个部分的1集中起来移到第一个2的前头即可，所以最终的字符串是这样的：
$$00\cdots011\cdots1 +（一个以2开头，由0和2构成的字符串）$$代码：（奇丑无比）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[100005];
int n0,n1;
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=1;(s[i]!='2')&&(i<=len);i++)n0+=s[i]=='0';
for(int i=1;(i<=len);i++)n1+=s[i]=='1';
for(int i=1;i<=n0;i++)putchar('0');
for(int i=1;i<=n1;i++)putchar('1');
bool f=0;
for(int i=1;(i<=len);i++){
f|=s[i]=='2';
if(f && s[i]!='1')putchar(s[i]);
}
return 0;
}
|
T3（此题代码调不对）
暴力推式子，每次操作对总合的贡献：
$$
\begin{aligned}
delta_i &=& &x\times n+d\times(\sum_{j=1}^{i-1} j+\sum_{j=1}^{n-i} j)\\
&=& &x\times n+d\times(\frac{i(i-1)}2+\frac{(n-i+1)(n-i)}2)\\
&=&&x\times n+d\times (2i^2-2(n+1)i+n(n+1))/2\\
\end{aligned}
$$在$i=int((n+1)/2)$取到最小值，$i=1$时取最大。所以在d<0时使其取最小，d>0时取最大即可。
代码：（错的，求大佬挑错）
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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m;
long double eve=0;
int main(){
scanf("%d%d",&n,&m);
int mid=(1.0+n)/2+0.5;
while(m--){
int x,d;
scanf("%d%d",&x,&d);
eve+=(long double)x;
long double delta=0;
if(d<0){
delta=(long double)d*(mid*(mid-1)+(n-mid+1)*(n-mid))/2;
delta/=n;
}
else{
delta=(long double)d*n*(n-1)/2;
delta/=n;
}
eve+=delta;
}
cout<<eve;
return 0;
}
|
T4
打了个暴力，结果wa了。。
代码：（有误）
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
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MXM=1e5+5;
int n,m;
int ans[MXM][2],cnt=0;
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int main(){
scanf("%d%d",&n,&m);
if(m<n-1){
printf("Impossible\n");
return 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++)
if(gcd(i,j)==1){
ans[++cnt][0]=i;
ans[cnt][1]=j;
if(cnt==m){
printf("Possible\n");
for(int k=1;k<=cnt;k++)printf("%d %d\n",ans[k][0],ans[k][1]);
return 0;
}
}
}
printf("Impossible\n");
return 0;
}
|
T5
这是一道组合题，设疲劳驾驶了$i$分钟才到达休息站的情况总共会被计算$f(i)$次。则这段路必定从休息站/起点开始，以休息站/终点结束，则：
$$f(i)=\left\{ \begin{aligned}
&2^{n-i}+(n-i-1)\times 2^{n-i-2}&(i\leq n-2)\\
&2^{n-i}&(i> n-2)
\end{aligned} \right.$$于是答案就等于$\sum_{i=1}^n f(i)\times sum[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
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NR=1e6+5;
const int P=998244353;
long long n;
long long arr[NR];
long long ans=0,tpn_i=1,tpn_i_2=1;
int main(){
scanf("%lld",&n);
for(long long i=1;i<=n;i++){
scanf("%lld",arr+i);
arr[i]=(arr[i]+arr[i-1])%P;
}
for(long long i=n;i>=1;i--){
if(i<=n-2){
ans+=((((n-i-1)*arr[i])%P)*tpn_i_2)%P;
ans%=P;
tpn_i_2=(tpn_i_2<<1)%P;
}
ans=(ans+(arr[i]*tpn_i)%P)%P;
tpn_i=(tpn_i<<1)%P;
}
printf("%lld",ans);
return 0;
}
|