Atcoder Beginner Contest 449
直接按题意输出即可。
Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
signed main()
{
cin>>n;
for(int i=n;i>=1;i--)
{
if(i!=1) cout<<i<<",";
else cout<<i;
}
return 0;
}
|
输入的时候注意不要输入i = 0的情况，随后按题意枚举即可（记得从西向东，因此吃了罚时）。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=102;
int n;
int a[maxn][maxn];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(i==j) continue;
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
for(int k=j+1;k<=n;k++)
{
if((a[i][j]+a[j][k])<a[i][k]) { cout<<"Yes"; return 0; }
}
}
}
cout<<"No";
return 0;
}
|
显然本题使用BFS最方便。BFS扩展去寻找每个连通块，若寻找到有在边上的连通块便打上tag。最终答案便是连通块数-打tag数。注意特判只有一个在边上的点的情况。赛时实现略为复杂。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1002;
int a[maxn][maxn],judge[maxn][maxn],tag[maxn*maxn];
int h,w,num;
char c;
struct nodd{
int x,y;
};
int x[10]={1,0,-1,0};
int y[10]={0,1,0,-1};
void getans(nodd pos)
{
queue<nodd> q;
q.push(pos);
while(!q.empty())
{
nodd now=q.front(); q.pop();
for(int i=0;i<=3;i++)
{
int tox=now.x+x[i];
int toy=now.y+y[i];
if((tox<1)||(tox>h)||(toy<1)||(toy>w)) continue;
if((a[tox][toy]==0)&&(judge[tox][toy]==0))
{
if((tox==1)||(toy==1)||(tox==h)||(toy==w)) tag[num]=1;
q.push(nodd{tox,toy}); judge[tox][toy]=1;
}
}
}
}
signed main()
{
cin>>h>>w;
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
cin>>c;
if(c=='#') a[i][j]=1;
else a[i][j]=0;
}
}
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
if(judge[i][j]==0 && a[i][j]==0)
{
judge[i][j]=1; num++;
getans(nodd{i,j});
if(i==1||i==h||j==1||j==w) tag[num]=1;
}
}
}
int len=num;
for(int i=1;i<=len;i++) if(tag[i]==1) num--;
cout<<num;
return 0;
}
|
体感是一道比较简单的D。首先对数组中每个值取模，然后排序。取模的原因就是我们想让处理后的最大值-最小值最小，所以就无脑先都加到对k取模之后的结果就行。随后我们对数组排序，如果不进行处理答案就是an − a1，我们想怎么让极差更小，其实对每个数字来说只可能加一次k，因为多加没有意义；而且只有从小到大连续都加k才有意义，比如说对a1, a3两个数都加k，显然不如a1, a2两个数都加k来的好。这样我们从1到n − 1依次枚举所有同时加k的区间，极差就是ai + k − ai + 1,我们可以在这个过程中维护极差的最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=300002;
int n,k;
int a[maxn];
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) { cin>>a[i]; a[i]%=k; }
sort(a+1,a+1+n);
int minn=a[n]-a[1];
for(int i=1;i<=n-1;i++) minn=min(minn,(a[i]+k)-a[i+1]);
cout<<minn;
return 0;
}
|
赛时做了不短时间，感觉很容易被绕进去。首先看到1e18的下标就知道要找结论了。观察可知，由于对于∀n > 2，有S[i] = s[i − 1] + s[i − 2]，我们可以发现S[i − 1]永远是S[i]的前缀。然后我们打表看看对于最小的斐波那契数列（a1 = 1, a2 = 1）有S[88] > 1e18，所以我们最多要考虑S的前88项就可。考虑到这个性质我们就可以考虑递归求解了。设f(n, now, c)是对于S[n]，前now个字符里字符c的数量，则有递归式： 其中，f(n − 1, lenn − 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
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=10005;
string a,b;
char c;
int q,l,r,lim;
int len[maxn],sum1[maxn][30],sum2[maxn][30],qzh[maxn][30];
int count(int n,int now)
{
if(now==0) return 0;
if(n==1) { return sum1[now][c-'a']; }
if(n==2) { return sum2[now][c-'a']; }
if(now<=len[n-1]) return count(n-1,now);
else return qzh[n-1][c-'a']+count(n-2,now-len[n-1]);
}
signed main()
{
cin>>a; cin>>b;
len[1]=a.size(); len[2]=b.size();
for(int i=3;i<maxn;i++)
{
if((len[i-1]+len[i-2])<1e18) len[i]=len[i-1]+len[i-2];
else { len[i]=len[i-1]+len[i-2]; lim=i; break; }
}
for(int i=0;i<=25;i++)
{
int len=a.size()-1;
for(int j=0;j<=len;j++)
{
if((j-1)>=0) sum1[j+1][i]=sum1[j][i];
if(i==(a[j]-'a')) sum1[j+1][i]++;
}
}
for(int i=0;i<=25;i++)
{
int len=b.size()-1;
for(int j=0;j<=len;j++)
{
if((j-1)>=0) sum2[j+1][i]=sum2[j][i];
if(i==(b[j]-'a')) sum2[j+1][i]++;
}
}
for(int i=0;i<=25;i++)
{
qzh[1][i]=sum1[len[1]][i];
qzh[2][i]=sum2[len[2]][i];
}
for(int i=3;i<=lim;i++)
{
for(int j=0;j<=25;j++)
{
qzh[i][j]=qzh[i-1][j]+qzh[i-2][j];
}
}
cin>>q;
while(q--)
{
cin>>l>>r>>c;
cout<<count(lim,r)-count(lim,l-1)<<endl;
}
return 0;
}
|
待补题。目前显然的想法是：由于有一条从N到1的链，其实就是问对于M条边，有几种选边方案，使得1到任何点都联通。且观察到题目保证了所有有向边都有u < v，所以我们应该给他转化为一个线段覆盖之类的问题，然后用dp解决。
