AtCoder Beginner Contest 146全题解
签到题没啥好说的
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int main()
{
string s;
cin>>s;
if(s=="SUN") puts("7");
else if(s=="MON") puts("6");
else if(s=="TUE") puts("5");
else if(s=="WED") puts("4");
else if(s=="THU") puts("3");
else if(s=="FRI") puts("2");
else if(s=="SAT") puts("1");
return 0;
}
|
同签到模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int main()
{
int n;string s;
cin>>n;cin>>s;
for(int i=0;i<s.size();i++)
{
char t=s[i]-'A';
int temp=t+n;
if(temp>=26) temp-=26;
cout<<char('A'+temp);
}
puts("");
return 0;
}
|
有编号$1-10^9$的物品 每个物品$N$的花费为$A\cdot N+B\cdot d(N)$元 其中$d(N)$数字$N$的位数 现在给定$X$元 求能买到编号最大的物品是多少
暴力枚举几位数即可 然后判断一下是否合法 注意只能判九位数 因为十位数只有一个$10^9$特殊判断即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
const int N=1000000000;
ll a,b,x;
int main()
{
cin>>a>>b>>x;
ll ans=0;
for(int i=1;i<=9;i++)
{
ll temp=x-b*i;
if(temp<=0) break;
ll t=temp/a;
if(t>=(ll)pow(10,i)) t=pow(10,i)-1;
ans=max(ans,t);
}
if(a*N+b*10<=x) ans=N;
cout<<ans<<endl;
return 0;
}
|
给定一棵树 树的每个点连着的边颜色都不能相同 问把所有边都染色最少需要几种颜色
首先最大值很好看 就是树最大的度 然后在染色的时候我们可以dfs（比赛时候这里退缩了一下然后跑去尝试构造浪费了大量时间）对于每条边我们把$u,v$按小大排一下直接放到pair里 然后从点1开始dfs 我们需要保存三个值 当前节点 父亲节点 以及父亲连到当前的颜色 然后我们扫描每条边从颜色1开始逐个相加 假如加到了父亲的颜色还要再加1跳过去 比赛时候被dfs时候处理边困了一下 明明一个map解决的事情
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
|
const int maxn=100050;
int n,in[maxn],res;
map<PII,int> co;
int head[maxn],num;
PII ans[maxn];
struct node{
int v,nex;
}e[maxn<<1];
void add(int u,int v)
{
e[++num].nex=head[u];
e[num].v=v;
head[u]=num;
}
void dfs(int u,int fa,int pre)
{
int c=1;
if(c==pre) c++;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa) continue;
co[make_pair(u,v)]=c;
res=max(res,c);
dfs(v,u,c);
c++;
if(c==pre) c++;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n-1;i++)
{
int x,y;
read(x),read(y);
if(x>y) swap(x,y);
ans[i]=make_pair(x,y);
add(x,y),add(y,x);
}
dfs(1,0,0);
cout<<res<<endl;
for(int i=1;i<=n-1;i++) cout<<co[ans[i]]<<endl;
return 0;
}
|
给定一个序列 假如这个序列的其中一个连续子段满足子段值的和模$K$等于子段长度则符合要求 求符合要求的子段的数目
这大概算是本场ABC最难的题？首先处理子段的不难想到前缀和 那么我们现在知道一段前缀和 如何去统计它的贡献呢 其实这是一个数学的活 首先假设当前考虑到$i$ 那么从$j+1$到$i$的子段和就是$sum(i)-sum(j)$ 区间长度是$i-j$ 题目要求的是 $(sum(i)-sum(j))%K=i-j$ 所以$i-j$的值肯定是在模$K$意义下的 即$i-j$属于$[0,K)$ 然后把式子魔改一波
$$sum(i)-sum(j)\equiv i-j \mod K$$
$$sum(i)-i\equiv sum(j)-j \mod K$$
到这里已经非常显然了 我们维护一个map 每次考虑到$i$看看$(sum(i)-i)%K$在map中有几个值就加几 再把自己加进map顺便注意考虑一下出界情况就行 因为$i-j\in[0,K)$
需要注意一下的是$j$要从0开始所以一开始就需要$mp[0]=1$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
const int maxn=200050;
ll n,k,sum[maxn];
map<ll,ll> mp;
ll ans;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) read(sum[i]);
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
mp[0]=1;
for(int i=1;i<=n;i++)
{
if(i>=k) mp[(sum[i-k]-(i-k))%k]--;
ans+=mp[(sum[i]-i)%k];
mp[(sum[i]-i)%k]++;
}
cout<<ans<<endl;
return 0;
}
|
给定一个从$0$到$n$的长为$n+1$的$01$序列 保证开头和结尾都是$0$每次最多向前进$m$个 而且只能走到为$0$的点 问能不能从开头走到结尾 假如能那么最少需要几次操作 并输出最小字典序的操作序列
这道题我看了几个题解好像都是dp？其实的话直接贪心即可 首先显然的结论假如有大于等于$m$个连续的1那么一定走不到 否则一定可以走到 因为它不连续 所以我总归可以至少跳到它前一个然后跳出去 之后我们考虑最少步数 直接贪心 每次先走$m$步 假如是1再往前退 这里为什么直接贪心不用dp呢 因为是不存在我前面比它跳的近后面又反超的情况的 因为跳的近的所能转移到的状态跳的远同样可以转移而且步数一定不会更坏 这里可以画图感受一下 然后由于保证字典序最小 所以自然倒序处理一波即可 剩下就是一些小细节了
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
|
int n,m;
string s;
vector<int> ans;
int main()
{
cin>>n>>m;
cin>>s;
int temp=0,flag=1;
for(int i=0;i<=n;i++)
{
if(s[i]=='1')
{
temp++;
if(temp>=m)
{
flag=0;
}
}
else temp=0;
}
if(!flag) puts("-1");
else
{
int temp=n;
while(temp)
{
if(s[max(temp-m,0)]=='0') ans.push_back(min(m,temp)),temp=max(temp-m,0);
else
{
int t=m;
while(s[temp-t]!='0') t--;
temp=temp-t;
ans.push_back(t);
}
}
for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<" ";
puts("");
}
return 0;
}
|