普及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;
int n,xs;
int main(){
scanf("%d",&n);
for(int i=n;i>=0;i--){
scanf("%d",&xs);
if(xs!=0){
if(i==n){
if(abs(xs)==1){
if(xs==-1)putchar('-');
}else printf("%d",xs);
}else if(i==1){
if(xs==1)printf("+x");
else if(xs==-1)printf("-x");
else printf("%+dx",xs);
continue;
}else if(i==0){
printf("%+d",xs);
break;
}else {
if(xs==1)printf("+");
else if(xs==-1)printf("-");
else printf("%+d",xs);
}
printf("x^%d",i);
}
}
printf("\n");
return 0;
}
普及T2 分数线划定
根据题目描述来模拟和排序即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
typedef pair<int,int> P;
P p[10005];
bool cmp(const P &pa,const P &pb){
return pa.first>pb.first||(pa.first==pb.first&&pa.second<pb.second);
}
int n,m,lim;
int main(){
scanf("%d%d",&n,&m);
lim=m*150/100;
for(int i=0;i<n;i++)
scanf("%d%d",&p[i].second,&p[i].first);
sort(p,p+n,cmp);
int sc=p[lim-1].first,extra=0;
for(int i=lim;i<n;i++)
if(p[i].first==sc)extra++;
else break;
printf("%d %d\n",sc,lim+extra);
for(int i=0;i<lim+extra;i++)
printf("%d %d\n",p[i].second,p[i].first);
return 0;
}
普及T3 细胞分裂
题意：找出某一个数$S_i$，使得$\mathcal S_i^T=M={m_1}^{m_2}$，且$T$最小。
考虑$S_i$的唯一分解，只要使得每一个质因数对应的次数都能超过$M$的唯一分解中这个质因数对应的次数即可。这样就可以算出对应的时间$T$来。
由于一个数的质因数个数大约是$O(logn)$级别的，使用以上算法的时间复杂度约为$O(nlogm_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
using namespace std;
typedef long long ll;
ll m1,m2,ans=-1,lis[10][2],a,tot,p,k;
int n,t=0;
int main(){
scanf("%d%lld%lld",&n,&m1,&m2);
ll e=m1;
for(ll b=2;b<=m1;b++)
if(e%b==0){
lis[t++][0]=b,lis[t-1][1]=0;
while(e%b==0)
lis[t-1][1]++,e/=b;
lis[t-1][1]*=m2;
}
for(int i=0;i<n;i++){
tot=0;
scanf("%lld",&a);
int j;
for(j=0;j<t;j++)
if(a%lis[j][0]==0){
p=0;
while(a%lis[j][0]==0)
p++,a/=lis[j][0];
k=lis[j][1]/p;
if(lis[j][1]%p)k++;tot=max(tot,k);
}else break;
if(j!=t)continue;
ans=(ans<0)?tot:(ans>tot?tot:ans);
}
printf("%lld\n",ans);
return 0;
}
普及T4 道路游戏
方法一
这是一道比较难的DP。
状态的表示比较难想，我个人一开始给出的转移方程是：
设$f(i,j,k)$表示当前在$i$工厂，$j$时间，$k$状态时的最大金币量，其中$k=0$表示当前机器人刚刚走出了第一步，$k=1$表示当前机器人走出了$2$到$p$步，并且已经被回收。
这样状态转移方程就很好写，$f(i,j,0)$就从上一秒的$f(i-1,j-1,1)$里面找最大值，$f(i,j,1)$就枚举一下步数。这么做的时间复杂度是$O(nmp)$的。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
using namespace std;
int dp[1005][1005][2]={0},m[1005][1005],n,t,p,cost[1005];
int deque[4005][2],f=0,r=0,R;
void in(int o,int at){
while(r>f&&o>deque[r-1][0])
r--;
deque[r][0]=o,deque[r++][1]=at;
}
int out(int at){
if(deque[f][1]==(at+R-p)%n)
f++;
return deque[f][0];
}
int main(){
scanf("%d%d%d",&n,&t,&p);
int i,j,m2=0,m3=0,k,l,ans=0,sum;
R=1000*n;
for(i=0;i<n;i++)
for(j=0;j<t;j++)
scanf("%d",&m[i][j]);
for(i=0;i<n;i++)
scanf("%d",&cost[i]);
for(i=1;i<=t;i++){//[f,r]
for(j=0;j<n;j++){
dp[i][j][1]=m2;
if(!j)dp[i][j][1]+=m[n-1][i-1]-cost[n-1];
else dp[i][j][1]+=m[j-1][i-1]-cost[j-1];
for(k=(j-1+n)%n,l=1,sum=0;l<p;l++,k=(k-1+n)%n)
if(i-l>0)
sum+=m[k][i-l],
dp[i][j][0]=max(dp[i][j][0],dp[i-l][k][1]+sum);
else break;
m3=max(m3,max(dp[i][j][0],dp[i][j][1]));
}
m2=m3,m3=0;
}
for(i=0;i<n;i++)
ans=max(ans,max(dp[t][i][0],dp[t][i][1]));
printf("%d\n",ans);
return 0;
}
但是居然过了！我就没留意这道题了（其实我都写了单调队列但没用上）
今天想了一下，发现没必要那么麻烦，很多地方可以优化。
方法二
设$f(i,j)$为机器人走到$i$工厂，$j$时间所能收集的最大金币量。那么
其中
那么提出$sum(i,j)$就可以发现括号里的量只与$k$有关，就用单调队列。而$sum$是可以前后递推出来的。
所以，解决本题的时间复杂度就优化为了$O(nm)$。
其实你如果读上面的题解读得仔细的话就会发现我没有讲到一个东西，那就是单调队列该怎么用。
本题的优化方式十分特殊，由于$sum$是斜方格形进行求和的（$i-k,j-k \rightarrow i,j$），所以单调队列的下标也要随着$i$改变而改变。具体可以看代码。
完了么？
没有。
很多题解都会被洛谷上的Extra Test卡掉，虽然我也不知道这数据怎么出的但反正很厉害。
（提示：其实读懂了题就不会被坑）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
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;
}
int n,m,p,coin[2005][1005],sum[1005][1005],cost[2005];
int Deque[1005][1005][2],f[1005],r[1005],maxi[1005];
int dp[1005][1005];
void init(){
n=read(),m=read(),p=read();
for(int i=0;i<n;i++)
for(int j=1;j<=m;j++)
coin[i][j]=coin[i+n][j]=read();
for(int i=0;i<n;i++)cost[i]=cost[i+n]=read();
}
void inque(int x,int val,int k){
while(r[x]>f[x]&&val>Deque[x][r[x]-1][0])r[x]--;
Deque[x][r[x]][0]=val,Deque[x][r[x]++][1]=k;
}
int outque(int x,int k){
while(r[x]>f[x]&&k-Deque[x][f[x]][1]>p)f[x]++;
return Deque[x][f[x]][0];
}
void solve(){
for(int i=0;i<n;i++)inque(i,-cost[i],0);
int R=1000*n; //R：当前单调队列的偏移量
for(int j=1;j<=m;j++){
R--;
sum[n-1][j]=sum[n-2][j-1]+coin[n-1][j];
sum[0][j]=sum[n-1][j-1]+coin[0][j];
dp[0][j]=outque(R%n,j)+sum[n-1][j];
maxi[j]=dp[0][j];
for(int i=1;i<n;i++){
sum[i][j]=sum[i-1][j-1]+coin[i][j];
dp[i][j]=outque((i+R)%n,j)+sum[i-1][j];
maxi[j]=max(maxi[j],dp[i][j]);
}
inque(R%n,maxi[j]-cost[0]-sum[n-1][j],j);
for(int i=1;i<n;i++)
inque((i+R)%n,maxi[j]-cost[i]-sum[i-1][j],j);
}
//以上把0单独处理了
printf("%d\n",maxi[m]);
}
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
32
33
34
using namespace std;
char f[27],sec[105],ori[105],s[105];
int flag=1,vis[27];
int main(){
scanf("%s%s%s",sec,ori,s);
int l1=strlen(sec),l2=strlen(s);
if(l1<26){
flag=0;goto end;
}//不够26个字母
for(int i=0;i<l1;i++){
if(f[sec[i]-'A']&&ori[i]!=f[sec[i]-'A']){
flag=0;goto end;
}//没对上
f[sec[i]-'A']=ori[i],vis[sec[i]-'A']=1;
}
for(int i=0;i<26;i++)
if(!vis[i]||!f[i]){
flag=0;goto end;
}//禁止没有得对
for(int i=0;i<26;i++)vis[f[i]-'A']++;
for(int i=0;i<26;i++)
if(vis[i]>2){
flag=0;goto end;
}//禁止一对多
end:
if(!flag)printf("Failed\n");
else {
for(int i=0;i<l2;i++)
printf("%c",f[s[i]-'A']);
printf("\n");
}
return 0;
}
提高T2 Hankson的趣味题
一道奇怪的数学题。
（理论上这题爆搜比正解快，数据好像不是很好）
考虑唯一分解和$GCD$，$LCM$的关系。设对于一个质数$p$，其为的一个因数。
那么：设为中$p$的次数。
则：因为，
若那么；若，那么.
若那么；若，那么.
然后根据这些条件，划定的取值范围。其实就是数轴上画区间。
对的每一个质因数都这么做一遍（因为它质因数种类最多），然后再用乘法原理把每一个的取值个数乘起来即可。
质因数分解可以用筛法预处理质数表实现，跑得飞快。
时间复杂度：$O(Tk)$？（$k$可能是个常数）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
using namespace std;
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;
}
int prime[5005],tot=0,vis[45001];
int lis[50][2],a0,a1,b0,b1,t,rec[50][2],ans;
int f(int &a,int b){
int res=0;
while(a%b==0)a/=b,res++;
return res;
}
void sieve(){
for(int i=2;i<=45000;i++){
if(!vis[i])
prime[tot++]=i;
for(int j=0;j<tot;j++){
if(i*prime[j]>45000)break;
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main(){
sieve();
for(int T=read();T;T--){
a0=read(),a1=read(),b0=read(),b1=read();
ans=1,t=1,lis[0][0]=lis[0][1]=1;
int e=b1;
for(int i=0;i<tot&&e>1;i++)
if(e%prime[i]==0)lis[t][0]=prime[i],lis[t++][1]=f(e,prime[i]);
if(e>1)lis[t][0]=e,lis[t++][1]=1;
//对b1分解，因为他的质数种类最多
rec[0][0]=rec[0][1]=1;
for(int i=1;i<t;i++){
int k=0,p=lis[i][0];
k=f(b0,p),rec[i][0]=rec[i][1]=lis[i][1];
if(k==lis[i][1])rec[i][0]=0;//kb0==kb1
k=f(a1,p),rec[i][0]=max(rec[i][0],k);
if(k<f(a0,p))
rec[i][1]=min(rec[i][1],k);//ka1<ka0，注意这里可能无解，所以取Min
}
if(a1!=1)printf("0\n");
else{
for(int i=0;i<t;i++)
if(rec[i][1]<rec[i][0]){
ans=0;break;
}else ans*=(rec[i][1]-rec[i][0]+1);
printf("%d\n",ans);
}
}
return 0;
}
提高T3 最优贸易
题意：找一条从$1 $到$n $的路径，使得经过的所有点中，最大点权和最小点权的差最大，并且最小点权应比最大点权早出现。
我们把这个路径分解一下，分解为$1\rightarrow a\rightarrow b\rightarrow n$。在$a $点买入，在$b $点卖出。因此我们可以考虑分别处理$1\rightarrow a$和$b\rightarrow n$，给每一个点维护一下从起点到他可经过的的最小点权和从他到终点可经过的最大点权。这样只要在正反图上各跑一次SPFA即可。
或者还可以先进行一次缩点，然后图就变成了一个DAG。这样只要在进行2次BFS即可。
综上，使用tarjan算法+BFS的情况下，时间复杂度为$O(n+m)$。
有趣的是，这种做法虽然理论上更优，实际上却不是。大概是我的代码常数太大了。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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
using namespace std;
int V,E,at[2][K],par[K],cnt[2]={0},tail[2][K];
int dfn[K],low[K],D=0,in[K],stack[K],top=0;
int mini[K],maxi[K],que[5*K],f,r;
typedef struct{
int v,_next;
}Edge;
Edge edge[2][KD];
void addedge(int _u,int _v,int o){
edge[o][cnt[o]].v=_v,
edge[o][cnt[o]]._next=at[o][_u];
if(at[o][_u]==-1)
tail[o][_u]=cnt[o];
at[o][_u]=cnt[o]++;
}
void tarjan_scc(int id){
dfn[id]=low[id]=++D;
in[id]=true;
stack[top++]=id;
int i=at[0][id],vv,t1,t2,_min,_max;
while(i!=-1){
vv=edge[0][i].v;
if(!dfn[vv])tarjan_scc(vv),low[id]=min(low[id],low[vv]);
else if(in[vv])low[id]=min(low[id],dfn[vv]);
i=edge[0][i]._next;
}
if(dfn[id]==low[id]){
t1=t2=-1,i=stack[top-1],_min=101,_max=-1;
do
vv=stack[--top],
in[vv]=false,
par[vv]=i,
edge[0][tail[0][vv]]._next=t1,
t1=at[0][vv],
edge[1][tail[1][vv]]._next=t2,
t2=at[1][vv],
_min=min(_min,mini[vv]),
_max=max(_max,maxi[vv]);
while(stack[top]!=id);
at[0][i]=t1,at[1][i]=t2;
mini[i]=_min,maxi[i]=_max;
}
}
void init(){
scanf("%d%d",&V,&E);
int i,j,u,v,o,c;
memset(at,-1,sizeof(at));
for(i=0;i<V;i++)
scanf("%d",&c),
mini[i]=maxi[i]=c;
for(i=0;i<E;i++){
scanf("%d%d%d",&u,&v,&o),
addedge(u-1,v-1,0),
addedge(v-1,u-1,1);
if(o==2)
addedge(v-1,u-1,0),
addedge(u-1,v-1,1);
}
for(i=0;i<V;i++)
par[i]=i;
tarjan_scc(0);
}
void solve(){
int h,vv,i,o,c,ans=0;
f=r=0,que[r++]=par[0];
memset(in,0,sizeof(in));
while(r-f){
h=que[f++];
for(i=at[0][h];i!=-1;i=edge[0][i]._next){
vv=par[edge[0][i].v];
if(mini[vv]>mini[h])
mini[vv]=mini[h],
in[vv]=1,
que[r++]=vv;
else if(!in[vv])
in[vv]=1,
que[r++]=vv;
}
}
f=r=0,que[r++]=par[V-1];
memset(dfn,0,sizeof(dfn));
while(r-f){
h=que[f++];
for(i=at[1][h];i!=-1;i=edge[1][i]._next){
vv=par[edge[1][i].v];
if(maxi[vv]<maxi[h])
maxi[vv]=maxi[h],
dfn[vv]=1,
que[r++]=vv;
else if(!dfn[vv])
dfn[vv]=1,
que[r++]=vv;
}
}
for(i=0;i<V;i++)
if(in[par[i]]&&dfn[par[i]])
ans=max(ans,maxi[par[i]]-mini[par[i]]);
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
提高T4 靶型数独
爆搜95分。加优化满分。DLX乱搞。
没什么好说的。这就是裸题。。。
优化：选择选择余地最小的格子开始搜。还有倒着搜。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
using namespace std;
int maxi=-1,vis[3][11][11]={0},sd[10][10]={0};
int lis[81][2],tot=0;
void get(int at){
int mini=99,p,x,y,o;
for(int i=at+1;i<tot;i++){
x=lis[i][0],y=lis[i][1],o=0;
for(int j=1;j<=9;j++){
if(vis[0][x][j]||vis[1][y][j]||vis[2][(x/3)*3+y/3][j])continue;
else o++;
}
if(o<mini)mini=o,p=i;
}
x=lis[at+1][0],y=lis[at+1][1];
lis[at+1][0]=lis[p][0],lis[at+1][1]=lis[p][1];
lis[p][0]=x,lis[p][1]=y;
}
int calc(){
int sum=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
if(i==4&&j==4)sum+=sd[i][j]*10;
else if(i>2&&j>2&&i<6&&j<6)sum+=sd[i][j]*9;
else if(i>1&&j>1&&i<7&&j<7)sum+=sd[i][j]*8;
else if(i>0&&j>0&&i<8&&j<8)sum+=sd[i][j]*7;
else sum+=sd[i][j]*6;
}
maxi=max(maxi,sum);
}//计算分数
void dfs(int at){
int x=lis[at][0],y=lis[at][1];
for(int i=1;i<=9;i++){
if(vis[0][x][i]||vis[1][y][i]||vis[2][(x/3)*3+y/3][i])continue;
vis[0][x][i]=vis[1][y][i]=vis[2][(x/3)*3+y/3][i]=1,sd[x][y]=i;
if(at<tot-1){
if(at!=tot-2)get(at);
dfs(at+1);
}else calc();
vis[0][x][i]=vis[1][y][i]=vis[2][(x/3)*3+y/3][i]=0,sd[x][y]=0;
}
}
//0 行 1 列 2 宫
int main(){
int tmp;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++){
scanf("%d",&tmp);
if(tmp){
sd[i][j]=tmp;
vis[0][i][tmp]=vis[1][j][tmp]=vis[2][(i/3)*3+j/3][tmp]=1;
}else lis[tot][0]=i,lis[tot++][1]=j;
}
dfs(0);
printf("%d\n",maxi);
return 0;
}