JXUFE_2017_寒假训练_warming_up_解题报告

传送门

思路

A

思路是这样的,考虑每个人都要被干掉,自己的战斗力先算上

然后对于每条边,边所连接的两人总有一个被先干掉,边必然会产生一个贡献

边的贡献取连接的两人中战斗力较小的就好了

我模拟了这个过程,写麻烦了,将就看233333

B

这题是算贡献的

假设S串不同,我们移动T串,易知T串的每个字符和S串的每个字符都对应了一次

然后S串每次循环时情况一样

所以我们开一个26的桶,统计一下T中每个字母的频数

遍历一边S串求出一次的贡献,总贡献就是一次贡献的n倍

然后该模多少模一下就好了

C

这题有个小坑,给的是站点,但票务计算要计算站区间233333

考虑到数据范围贼小,暴力模拟一下就好了

P.S. 大数据范围需要区间修改线段树了,在此不赘述

D

我都不知道我的做法对不对233333

时间复杂度是$O(nlog_2^2n)$

首先需要给所有的订单排序,结束时间早的放前面,结束时间相同要求时间短的放前面

然后我们考虑类似于$O(nlog_2n)$的$LIS$的做法来DP

假设$dp[i]$表示完成了i个任务最快需要多久

对于每一个任务,我们算出它的最晚进行时间,也就是令$T_e=T_2-T_1$

然后假设当前最多完成了$m$个任务,

如果$dp[m]<=T_e$,那么最多完成的任务数($m$)+1,同时记下这个任务

如果不行,我们需要知道完成几个任务之后可以完成当前任务

这里需要二分一下,然后我们与此同时还要记下前$i$个已完成的任务的$T_1$最大值,考虑可修改,于是树状数组


自此整道题需要重新思考


我们重新定义$dp[i]$为完成了前i个任务最快情况下第$i$个任务的所需时间

然后用树状数组统计前缀和,这样二分的时候复杂度是$O(log_2^2n)$

与此同时我们依然需要树状数组维护前$m$个任务的前缀最大值,这个维护也是$O(log^2_2n)$

继续刚才的思路,如果这个任务可以再已有的基础上继续完成,我们就继续完成就好了

否则的话二分出一个$k$,使得前k个任务的完成时间不大于$T_e$

同时前$k+1$个任务的完成时间大于$T_e$

然后我们用当前任务和前$k+1$个任务比较,如果当前任务的所需时间小于前$k+1$个任务的中最大的那个任务的所需时间,我们就用当前任务去更新


这样下去,最后统计得出的$m$为我们最多能送出多少份订单

输出$n-m$就是最少会收到多少份差评了

思路较复杂,运气好,用了两个树状数组硬莽过去了

E

注意到一个事实,我们对于一个$x$位数,决定它是不是回文数的只是后$\frac{x}{2}$位

因此我们发现最多从$n$向下枚举到$n-10^5$左右就能得到答案,暴力就好了呀

F

DFS直接暴力,剪剪枝就可以剪过去了

G

考虑自己的排名很小的情况,可以直接优先队列模拟

那么自己排名很大的时候,我们可以用二分去逼近

二分逼近到某一时刻正在安检和已经安检完毕的人刚好小于$x$

且下一时刻正在安检和已经安检完毕的人数不小于$x$

然后我们对每个门计算一下它目前安检的进度,拿优先队列跑若干轮就解决了

代码

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
struct node
{
int to;
LL cost;
};
queue<int> q;
vector<node> g[1005];
int tot[1005];
int i,j,k,l,m,n;
LL a[1005];
LL ans;

int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
scanf("%d",&m);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
if(a[x]<a[y] || (a[x]==a[y] && x>y)){k=x;x=y;y=k;}
struct node t;
t.to=y;t.cost=a[y];
tot[y]++;
g[x].push_back(t);
}
while(!q.empty())q.pop();
for(i=1;i<=n;i++)
if(tot[i]==0){q.push(i);tot[i]=-1;}
while(!q.empty())
{
k=q.front();q.pop();
ans+=a[k];
for(i=0;i<g[k].size();i++)
{
j=g[k][i].to;
tot[j]--;
ans+=g[k][i].cost;
if(tot[j]==0){q.push(j);tot[j]=-1;}
}
}
printf("%lld",ans);
return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const LL mod=1e9+7;

char s1[1000005],s2[1000005];
LL a[30];
LL i,n;

int main()
{
gets(s1+1);gets(s2+1);
n=strlen(s1+1);
for(i=1;i<=n;i++)a[s1[i]-64]++;
LL ans=0;
for(i=1;i<=n;i++)
ans+=a[s2[i]-64];
ans*=n;
printf("%lld",ans%mod);
return 0;
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[105];
int i,j,k,l,m,n;

int main()
{
scanf("%d%d%d",&n,&k,&m);
for(i=1;i<=n-1;i++)a[i]=k;
while(m--)
{
k=2000;
int x,y;
scanf("%d%d",&x,&y);
for(i=x;i<=y-1;i++)k=min(k,a[i]);
if(k<1){printf("No\n");continue;}
printf("Yes\n");
for(i=x;i<=y-1;i++)a[i]--;
}
return 0;
}

D

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
const int maxn=100005;

struct node
{
LL num;
int pos;
node(LL num=0,int pos=0):num(num),pos(pos){}
bool operator > (const struct node p)const
{return num>p.num || (num==p.num && pos<p.pos);}
}ma[maxn],f[maxn];
struct wm
{
LL ne,en;
bool operator < (const struct wm p)const
{return en<p.en || (en==p.en && ne<p.ne);}
}a[maxn];

int i,k,m,n;
LL sum[maxn];
LL b[maxn];

void csum(int po,LL nu)
{
while(po<=n)
{
sum[po]+=nu;
po+=lowbit(po);
}
}

void cmax(int po)
{
while(po<=n)
{
f[po]=ma[po];
for(int i=1;i<lowbit(po);i<<=1)
if(f[po-i]>f[po])f[po]=f[po-i];
po+=lowbit(po);
}
}

void change(int po,LL nu)
{
csum(po,nu-b[po]);
b[po]=nu;
ma[po]=node(nu,po);
cmax(po);
}

LL findsum(int x)
{
LL aa=0;
while(x>0)
{
aa+=sum[x];
x-=lowbit(x);
}
return aa;
}

struct node findmax(int x)
{
struct node tt=node(0,0);
while(x>0)
{
if(f[x]>tt)tt=f[x];
x-=lowbit(x);
}
return tt;
}

int find(LL o)
{
int l=1,r=m;
while(r-l>1)
{
int mid=(l+r)>>1;
if(findsum(mid)>o)r=mid;else l=mid;
}
if(findsum(l)>o)l--;
if(l<m && findsum(l+1)<=o)l++;
return l;
}

int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lld%lld",&a[i].ne,&a[i].en);
sort(a+1,a+n+1);
m=1;change(1,a[1].ne);
for(i=2;i<=n;i++)
{
LL temp=a[i].en-a[i].ne;
LL tot=findsum(m);
if(temp>=tot)
{
m++;
change(m,a[i].ne);
continue;
}
k=find(temp)+1;
struct node tt=findmax(k);
if(tt.num>a[i].ne)change(tt.pos,a[i].ne);
}
printf("%d",n-m);
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
int a[15];
int n,m,k,i;
bool f;

int main()
{
scanf("%d",&n);
while(n>0)
{
m=n;k=0;
while(m>0)
{
k++;
a[k]=m%10;m/=10;
}
f=true;
for(i=1;i<=k;i++)
if(a[i]!=a[k+1-i]){f=false;break;}
if(f)break;
n--;
}
printf("%d",n);
return 0;
}

F

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
struct node
{
int len,num;
node(int len=0,int num=0):len(len),num(num){}
}dp[105][11];

struct edge
{
int to,cost;
edge(int to=0,int cost=0):to(to),cost(cost){}
};
vector<edge> g[105];
bool vis[105];
int i,j,k,l,m,n,st,en,p;
int a1,a2;

void DFS(int x,int y,int tot)
{
if(y>p || vis[x] || tot>a1 || (x==en && y<p))return;
if(x==en && y==p)
{
if(tot>a1)return;
if(tot==a1){a2++;return;}
a1=tot;a2=1;
return;
}
vis[x]=true;
for(unsigned int t=0;t<g[x].size();t++)DFS(g[x][t].to,y+1,tot+g[x][t].cost);
vis[x]=false;
}

int main()
{
while(scanf("%d%d%d%d%d",&n,&p,&st,&en,&m)==5)//p steps
{
for(i=1;i<=n;i++)g[i].clear();
while(m--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
g[x].push_back(edge(y,z));
}
memset(vis,0,sizeof(vis));
a1=1<<29;a2=0;
DFS(st,1,0);
if(a1==1<<29)printf("-1\n");else printf("%d %d\n",a1,a2);
}
return 0;
}

G

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
LL a[1005];
int i,j,k,l,m,n,T;
LL x,y,z;
LL sum,tot,ans;

struct node
{
LL en;
int pos;
bool operator < (const struct node p)const
{return en>p.en || (en==p.en && pos>p.pos);}
};

LL cal(LL t)
{
LL o=0;
for(int i=1;i<=n;i++)
if(t%a[i]==0)o+=t/a[i];else o+=t/a[i];
o+=n;
return o;
}

priority_queue<node> q;

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&n,&z);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
x=0;y=z*a[1];
while(y-x>1)
{
LL mid=(x+y)>>1;
if(cal(mid)>=z)y=mid;else x=mid;
}
if(cal(y)>=z)x=y-1;else x=y;
tot=cal(x);ans=1e18;
while(!q.empty())q.pop();
if(z>n)
{
for(i=1;i<=n;i++)
{
struct node t;
if(x%a[i]==0)y=x+a[i];
else y=(x/a[i]+1)*a[i];
t.en=y;t.pos=i;
q.push(t);
}
while(tot<z-1)
{
tot++;
struct node te=q.top();
q.pop();
te.en+=a[te.pos];
q.push(te);
}
}else
{
for(i=1;i<=n;i++)
{
struct node t;
if(x%a[i]==0)y=x+a[i];
else y=(x/a[i]+1)*a[i];
if(i>=z)y=0;
t.en=y;t.pos=i;
q.push(t);
}
}
sum=1005;
while(sum--)
{
struct node te=q.top();q.pop();
te.en+=a[te.pos];
ans=min(ans,te.en);
q.push(te);
}
printf("%lld\n",ans);
}
return 0;
}