普及T1 数字统计
某一道普及的弱化版。
模拟即可。1
2
3
4
5
6
7
8
9
10
11
12
using namespace std;
int l,r,ans=0;
int main(){
scanf("%d%d",&l,&r);
for(int i=l;i<=r;i++){
int t=i;
while(t)ans+=(t%10==2),t/=10;
}
printf("%d\n",ans);
return 0;
}
普及T2 接水问题
模拟即可。
可以用堆加速，但我的代码里没用。
不用堆的时间复杂度是$O(nm)$，用的话是$O(nlogm)$。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
using namespace std;
int n,m,at[105],w[10005],f=0,ans=0;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d",&at[i]);
for(int i=m;i<n;i++)
scanf("%d",&w[i-m]);
for(;;){
int mini=INF;
for(int i=0;i<m;i++)
if(at[i]>0&&at[i]<mini)mini=at[i];
if(mini==INF)break;
ans+=mini;
for(int i=0;i<m;i++)
if(at[i]>0){
at[i]-=mini;
if(!at[i]){
if(f!=n-m)at[i]=w[f++];
else at[i]=-1;
}
}
}
printf("%d\n",ans);
return 0;
}
普及T3 导弹拦截
此题致敬了11年前的那道经典题目。
我们希望这个工作半径最小，直觉上就要让这两个系统都被充分利用。也就是让第一套拦截一部分，第二套拦截另一部分。
我们先对所有导弹到第一套系统的距离从近到远排一个序，企图把这个序列切成$2$份，将前半部分给第一个系统，将后半部分（远的）给第二个系统。
枚举切开的部位，找到第二套系统应该有的工作半径，也就是分配给第二套系统的最远导弹到他的距离。这里用各种方法实现，我用的是对所有导弹到第二套系统的距离从远到近排一个序，然后用一个指针扫的方法。
综上，解决本题的时间复杂度为$O(nlogn)$。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
using namespace std;
typedef struct{
int id,dis;
}Mis;
Mis mis[200005];
bool operator<(Mis a,Mis b){return a.dis<b.dis;}
int p1[2],p2[2],n,at;//p1 x p2 y
bool vis[100005]={0};
int ask(){//找第二套应该有的工作半径
while(vis[mis[at].id]&&at<2*n)
at++;
if(at==2*n)return 0;
else return mis[at].dis;
}
int main(){
scanf("%d%d%d%d%d",&p1[0],&p2[0],&p1[1],&p2[1],&n);
int i,j,l1,l2,ans=2000000000;
for(i=0;i<n;i++)
scanf("%d%d",&l1,&l2),
mis[i].dis=(p1[0]-l1)*(p1[0]-l1)+
(p2[0]-l2)*(p2[0]-l2),
mis[i+n].dis=-(p1[1]-l1)*(p1[1]-l1)-
(p2[1]-l2)*(p2[1]-l2),
mis[i].id=mis[i+n].id=i;
sort(mis,mis+n),
sort(mis+n,mis+n+n),
at=n;
ans=min(ans,-ask());//全部分配给第二套
for(i=0;i<n;i++)
vis[mis[i].id]=1,
ans=min(ans,(mis[i].dis-ask()));
printf("%d\n",ans);
return 0;
}
普及T4 三国游戏
这个人肯定不会输给电脑。
因为计算机的选将是完全根据这个人的选法来的，也就是说，这个人自己是一定有把握选中更好的策略的。
然后具体选法，非常简单：
最大的一定被拆，所以我们矮子里拔高个儿，选默契值排第二且是所有第二中最高的一对将。
这样就做完了。
时间复杂度：$O(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
using namespace std;
typedef long long ll;
int n,mat[505][505]={0};
void init(){
scanf("%d",&n);
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
scanf("%d",&mat[i][j]),
mat[j][i]=mat[i][j];
}
void solve(){
int max1=0,max2=0,ans=0;
for(int i=0;i<n;i++){
max1=max2=0;
for(int j=0;j<n;j++){
if(mat[i][j]>max1)max2=max1,max1=mat[i][j];
else if(mat[i][j]>max2)max2=mat[i][j];
}
ans=max(ans,max2);
}
printf("1\n%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
提高T1 机器翻译
用队列模拟即可。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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
bool vis[1005];
int w,m,n,que[100005],f=0,r=0;
void init(){
m=read(),n=read();
}
void solve(){
int ans=0;
while(n--){
w=read();
if(!vis[w]){
vis[w]=1,que[r++]=w,ans++;
if(r-f==m+1)vis[que[f++]]=0;
}
}
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
提高T2 乌龟棋
按卡片数$DP$即可。只要知道每一种卡片的使用情况就可以推知当前所处位置，从而进行状态转移。
设$f(i,j,k,l)$表示用了$i$张$1$，$j$张$2$，$k$张$3$，$l$张$4$的最大得分，则状态转移方程容易导出。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
using namespace std;
int dp[41][41][41][41]={0},n,m,cnt[4]={0},score[353];
int main(){
scanf("%d%d",&n,&m);
int i,j,u,v,d;
for(i=1;i<=n;i++)
scanf("%d",&score[i]);
for(i=0;i<m;i++)
scanf("%d",&j),cnt[j-1]++;
dp[0][0][0][0]=score[1];
fep(i,0)fep(j,1)fep(u,2)fep(v,3){
d=dis(i,j,u,v);
if(i)dp[i][j][u][v]=max(dp[i-1][j][u][v]+d,dp[i][j][u][v]);
if(j)dp[i][j][u][v]=max(dp[i][j-1][u][v]+d,dp[i][j][u][v]);
if(u)dp[i][j][u][v]=max(dp[i][j][u-1][v]+d,dp[i][j][u][v]);
if(v)dp[i][j][u][v]=max(dp[i][j][u][v-1]+d,dp[i][j][u][v]);
}
printf("%d\n",dp[cnt[0]][cnt[1]][cnt[2]][cnt[3]]);
return 0;
}
提高T3 关押罪犯（待考察）
贪心。
将仇恨值从大到小排序，从仇恨最大的一对人开始处理起。记录每一个人的“对手”，看作是这个人和“对手”必须处在不同监狱。如果两人所处监狱相同那就表示分配到此为止，输出答案。
然后分类讨论，假设两人都还没有对手就互相记为对手，表示两人不会在一个监狱；只有一个人有对手，那就另一个人把这个人记为对手，并且把这个人的对手收为己方（用并查集实现）；两个人都有，那就收各自的对手为己方。
讨论完之后，处理下一对罪犯，如此反复。
这样就可以在$O(mlogm)$的时间复杂度内解决这个问题。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
using namespace std;
int parent[20005],riv[20005]={0},m,n,re[100005][3];
int cmp(const void *a,const void *b){
return *(int*)b-*(int*)a;
}
void init(int k){
for(int i=1;i<=k;i++)parent[i]=i;
}
int Find(int a){
if(parent[a]==a)return a;
return (parent[a]=Find(parent[a]));
}
void joint(int x,int y){
int a=Find(x),b=Find(y);
if(a==b)return;
parent[b]=a;
}
int main(){
scanf("%d%d",&n,&m);
init(n);int i,k1,k2,t1,t2;
for(int i=0;i<m;i++)
scanf("%d%d%d",&re[i][1],&re[i][2],&re[i][0]);
qsort(re,m,sizeof(re[0]),cmp);
for(i=0;i<m;i++){
t1=re[i][1],t2=re[i][2];
if(Find(t1)==Find(t2))break;
if(riv[t2]&&!riv[t1])swap(t1,t2);
if(!riv[t2]){
if(!riv[t1])riv[t1]=t2,riv[t2]=t1;
else riv[t2]=t1,joint(t2,riv[t1]);
}else
joint(t2,riv[t1]),joint(t1,riv[t2]);
}
if(i==m)printf("0\n");
else printf("%d\n",re[i][0]);
return 0;
}
提高T4 引水入城
先搜索，搜出每一个出水站能最多支援几个国家。
然后会发现每一个国家能支援到的国家一定是一段一段存在的。
如果不是，那么会形成一些国家无法被到达的局面，就输出$0$，然后统计。
否则对每段区间排序后贪心选择即可。
可以用一些手段加速，如对在第一行的国家，只选取相对周围的国家更高一些的国家来搜索，因为这个国家肯定可以向两侧扩展。
时间复杂度：$O(nm)$（近似）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
76
using namespace std;
bool dp[505][505],able[505][505]={0};
int n,m,h[505][505],par[505],res,ans,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int stack[250005][2],top=0;
void dfs(int x,int y){
int nx,ny,i;
stack[top][0]=x,stack[top++][1]=y;
while(top){
x=stack[--top][0],y=stack[top][1];
for(i=0;i<4;i++){
nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m&&
h[nx][ny]<h[x][y]&&!dp[nx][ny])
dp[nx][ny]=1,stack[top][0]=nx,stack[top++][1]=ny;
}
}
}
void _solve(){
int i,j,p,k,rec[505][2],tot=0,l,r;
for(ans=1,i=j=0;j<m;j++){
while(i<m&&par[i]==par[j])i++;
p=par[i-1],k=0;
while(k<m&&!able[p][k])k++;
rec[tot][0]=k;
if(tot&&rec[tot-1][0]==k)tot--;
while(k<m&&able[p][k])k++;
rec[tot++][1]=k-1;
if(k-1<rec[tot-1][0])tot--;
j=i-1;
}
for(l=rec[0][0],r=rec[0][1],i=1;i<tot;i++){
while(i<tot&&rec[i][0]<=r+1)i++;
if(r==m-1)break;
i--,r=rec[i][1],ans++;
}
}
void solve(){
int i,j,k;
for(i=j=0;j<m;j++){
while(i<m&&par[i]==par[j])i++;
memset(dp,0,sizeof(dp));
dp[0][par[i-1]]=1,dfs(0,par[i-1]);
memcpy(able[par[i-1]],dp[n-1],sizeof(bool)*m);
j=i-1;
}
bool cnt[505]={0};
for(k=i=0;i<m;i++)
for(j=0;j<m;j++)
if(able[par[i]][j]&&!cnt[j])cnt[j]=1,k++;
res=(k==m)?1:0;
if(res)_solve();
else ans=m-k;
printf("%d\n%d\n",res,ans);
}
int main(){
scanf("%d%d",&n,&m);
int i,j,maxi,lst;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&h[i][j]);
for(i=0;i<m;i++){
while(i<m-1&&h[0][i+1]>h[0][i])i++;
for(j=i-1;j>=0&&h[0][j]<h[0][j+1];j--)
par[j]=i;
par[i]=i;
for(j=i+1;j<m&&h[0][j]<h[0][j-1];j++)
par[j]=i;
while(i<m-1&&h[0][i+1]<h[0][i])i++;
}
solve();
return 0;
}