Atcoder Beginner Contest 451
根据题意直接判断字符串长度是否等于5，按要求输出即可。
Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
signed main()
{
cin>>s;
int len=s.size();
if(len%5==0) cout<<"Yes";
else cout<<"No";
return 0;
}
|
将部门编号作为下标建立数组tong，对于每条输入，tong[Ai] − −, tong[Bi] + +,最后输出数组中所有值即可。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000002;
int n,m,a,b;
int tong[maxn];
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
tong[a]--; tong[b]++;
}
for(int i=1;i<=m;i++) cout<<tong[i]<<endl;
return 0;
}
|
题目要求维护两个操作，插入一个带权元素与删除小于某个权值的所有元素。观察数据范围可知题目需要log级别的算法。我们维护一个优先队列，插入直接插入，删除的时候只需要重复判断堆顶元素和删除阈值的大小关系即可，这样就避免了重复访问。复杂度O(QlogQ)。用实现时可以选择重载运算符或直接插入负值。
Code:
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000002;
int t,h,op;
priority_queue<int> q;
signed main()
{
cin>>t;
while(t--)
{
cin>>op>>h;
if(op==1) q.push(-h);
if(op==2)
{
while(!q.empty())
{
int now=q.top();
if(-now<=h) q.pop();
else break;
}
}
cout<<q.size()<<endl;
}
return 0;
}
|
首先观察数据范围得到N < 1e9，于是我们知道由拼接构成N的每个部分都是不会超过1e9的。所以我们直接预处理出所有可能的“拼图”，之后直接暴搜+剪枝（超过1e9便不继续搜索）便足以通过本题。
Code:
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100;
int n,tot,total;
int a[maxn],len[maxn],final[10000002],vis[maxn],p10[12];
int getLen(int now)
{
int sum=0;
while(now)
{
sum++;
now/=10;
}
return sum;
}
set<int> mp;
void dfs(int now)
{
if(now>0 && mp.count(now)==0)
{
final[++total]=now;
mp.insert(now);
}
for(int i=1;i<=tot;i++)
{
int nxt=a[i]+now*p10[len[i]];
if(nxt<=1e9) dfs(nxt);
}
}
signed main()
{
cin>>n;
for(int i=0;i<=50;i++)
{
if((1<<i)<=1e9) a[++tot]=pow(2,i);
else break;
}
p10[0]=1;
for(int i=1;i<=10;i++) p10[i]=p10[i-1]*10;
for(int i=1;i<=tot;i++) len[i]=getLen(a[i]);
dfs(0); sort(final+1,final+1+total);
cout<<final[n];
return 0;
}
|
首先我们观察一个性质，对于所有aij里面最小的那一个，肯定是要把i, j直接连起来的，且边权为aij。这个结论是易证的，因为首先树上两点之间的路径仅有一条，如果能够满足i, j通过其他点（假设为点z）连起来且满足边权要求，则最后肯定不满足i, z; z, j之间的边权要求，因为i, j是距离要求最小的一对点。所以我们推广这个结论，即如果有ai, j < am, n，一定要优先满足i, j之间的边权要求。所以我们直接按照ai, j大小排序，如果两个点已经联通了，那么就跳过这条边（他们能联通肯定是为了满足前面边权更小的点对更严苛的要求）最后check是否满足距离和题目要求相同；如果两个点还没有联通，因为我们考虑到的这一对点已经是当前aij最小的点对了，我们肯定要把这一对点直接连起来（这个结论就是最开始证明的结论）。这个维护连通性的过程可以由并查集完成，在最后以每个点为根分别进行一次dfs完成check工作即可。时间复杂度O(n2logn)。
Code：
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3002;
struct nodd {
int u,v,val;
}edge[maxn*maxn];
struct nodd2 {
int to,val;
};
vector<nodd2> tree[maxn];
int n,tot,flag;
int a[maxn][maxn],fa[maxn],final[maxn][maxn],dis[maxn];
bool cmp(nodd x,nodd y) { return x.val<y.val; }
int find(int x)
{
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
void dfs(int now,int dep,int f)
{
dis[now]=dep;
int len=tree[now].size()-1;
for(int i=0;i<=len;i++)
{
int to=tree[now][i].to;
if(to==f) continue;
dfs(to,dep+tree[now][i].val,now);
}
return ;
}
signed main()
{
cin>>n;
for(int i=1;i<=n-1;i++)
{
for(int j=i;j<=n;j++)
{
if(i==j) continue;
cin>>a[i][j]; a[j][i]=a[i][j];
edge[++tot]=nodd{i,j,a[i][j]};
}
}
for(int i=1;i<=n;i++) fa[i]=i;
sort(edge+1,edge+1+tot,cmp);
for(int i=1;i<=tot;i++)
{
if(find(edge[i].u)!=find(edge[i].v))
{
fa[find(edge[i].u)]=find(edge[i].v);
tree[edge[i].u].push_back(nodd2{edge[i].v,edge[i].val});
tree[edge[i].v].push_back(nodd2{edge[i].u,edge[i].val});
}
}
for(int i=1;i<=n;i++)
{
memset(dis,0,sizeof(dis)); dfs(i,0,0);
for(int j=1;j<=n;j++) if(dis[j]!=a[i][j]) flag=1;
}
if(flag==1) printf("No");
else printf("Yes");
return 0;
}
|
待补题，赛时思考方向是要用并查集在线的去维护不同连通块的一些性质的。
