第一次完整的打下来一场比赛。
| Solved | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 7/7 | O | O | O | O | O | Ø | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
比赛链接
F
题目大意
给定一段长度$\leq1500$的序列，求一组互不相交的子序列，使得每个子序列内数字之和相等，问这一组子序列最多包含多少个子序列。
解题思路
先储存所有子序列和的可能性，再从左往右枚举右端点，枚举左端点，贪心地添加区间信息。
AC代码
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;
int n;
int a[1600],s[1600];
vector<int>G;
struct Ans{
int num,r;//r:上一组区间的右端点
vector<pair<int,int> >vec;
}ans[1125080];
int f(int x){return lower_bound(G.begin(),G.end(),x)-G.begin();}
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
for(i=1;i<=n;i++)for(j=i;j<=n;j++)G.push_back(s[j]-s[i-1]);
sort(G.begin(),G.end());
G.erase(unique(G.begin(),G.end()),G.end());
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
int su=s[i]-s[j-1];
int p=f(su);
if(ans[p].r<j){
ans[p].r=i;
ans[p].num++;
ans[p].vec.push_back({j,i});
}
}
}
int mx=-1e9,temp=0;
for(i=0;i<G.size();i++)
if(ans[i].num>mx)mx=ans[i].num,temp=i;
printf("%d\n",mx);
for(i=0;i<ans[temp].vec.size();i++)
printf("%d %d\n",ans[temp].vec[i].first,ans[temp].vec[i].second);
return 0;
}
G
题目大意
给一棵树，给边染色，对任意一个节点，如果连着多个同样颜色的边就称之为“坏点”，问“坏点”不超过$k$个需要染色的色数最少是多少，并输出一种染色方案。
解题思路
题意理解了半天没搞懂，导致最后没有AK对于“非坏点”，所有连接它的边都是不同颜色的，所以色数是第$k$大度数的点的度数。
然后xjb染就行了。AC代码
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;
struct Edge{
int end,near;
}e[N<<1];
int head[N],cnt=1;
void add(int a,int b){
e[++cnt].end=b;e[cnt].near=head[a];head[a]=cnt;
}
int deg[N],mx,col[N<<1];
void dfs(int c,int p,int f){
int i,q;
for(i=head[p];i;i=e[i].near){
q=e[i].end;
if(q==f)continue;
col[i>>1]=(++c)%mx;
dfs(c,q,p);
}
}
int main(){
int i,n,k,x,y;
scanf("%d%d",&n,&k);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x),deg[x]++,deg[y]++;
sort(deg+1,deg+n+1);
printf("%d\n",mx=deg[n-k]);
dfs(1,1,0);
for(i=1;i<n;i++)printf("%d ",col[i]+1);
return 0;
}