Atcoder Beginner Contest 452
直接按照题目要求判断即可。可以注意到，对于3、5、7、9月都是月份等于日期，所以加几个特判就好。
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
int n,m;
signed main()
{
cin>>n>>m;
if(n==1 && m==7) { cout<<"Yes"; return 0; }
if(n==m&&(n%2==1)&&(n!=11)&&(n!=1)) cout<<"Yes";
else cout<<"No";
return 0;
}
|
按照题目要求输出矩阵即可（多来点这种不用读题的T2好不好）。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000002;
int n,m;
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i==1||j==1||i==n||j==m) cout<<"#";
else cout<<".";
}
cout<<endl;
}
return 0;
}
|
B题不用读洋文，代价就是C被洋文折磨10min（大嘘）。
对于每个给出的字符串，如果长度不等于n肯定就不行，如果等于n怎么处理呢？我们预处理出一个数组，这个数组每个元素代表对第i个要求，满足的字符串是否存在。预处理出这个之后我们枚举每个字符串作脊椎，依次判断n个要求能否满足即可。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200005;
int n,m;
int a[maxn],b[maxn];
string s[maxn];
int judge[15][30];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>s[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[j].size()==a[i])
{
int char_idx=s[j][b[i]-1]-'a';
judge[i][char_idx]=1;
}
}
}
for(int i=1;i<=m;i++)
{
int len=s[i].size();
if(len!=n)
{
cout<<"No\n";
continue;
}
int flag=0;
for(int j=0;j<len;j++)
{
if(judge[j+1][s[i][j]-'a']==0)
{
flag=1;
break;
}
}
if(flag==1) cout <<"No\n";
else cout <<"Yes\n";
}
return 0;
}
|
首先观察数据范围，第二个字符串的长度是小于50的。我们考虑如何统计答案数量，如果每个点，我们能统计出来在右边的哪个位置，第一次能把T完整的匹配下来，那么对于作为左端点的所有情况，答案就是
。如果在最右侧都匹配不到，那么答案就加上。考虑怎么获得这个最右边第一次匹配整个T的位置，代表对于位置i，往右匹配T，在哪个位置能把T的所有部分全都匹配完。然后我们就可以从右往左去更新这个dp数组。具体的状态转移方程见代码，已经很清晰了。时间复杂度。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200005;
string s,t;
int dp[maxn][55],ans;
signed main()
{
cin>>s>>t;
int len1=s.size(),len2=t.size(); len1--; len2--;
for(int i=0;i<maxn;i++)
{
for(int j=0;j<55;j++) dp[i][j]=-1;
}
for(int i=len1;i>=0;i--)
{
for(int j=0;j<=len2;j++) dp[i][j]=dp[i+1][j];
for(int j=0;j<=len2;j++)
{
if((dp[i+1][j+1]!=-1)&&(s[i]==t[j])) dp[i][j]=dp[i+1][j+1];
if((j==len2)&&(s[i]==t[j])) dp[i][j]=i;
}
}
for(int i=0;i<=len1;i++)
{
if(dp[i][0]!=-1) ans+=(dp[i][0]-i);
else ans+=(len1-i+1);
}
cout<<ans;
return 0;
}
|
很shabi的Sigma计数题。首先对于,可以公式地转化为，所以我们计数的目标就是： 稍微化简一下，就是：
我们发现，前半部分直接可以计算出来，对于后半部分，如果j的值是确定的，在这一部分，其实是以j为周期循环的。所以我们预处理出来的前缀和数组，就可以快速地在调和级数级别处理出来后面这一大项。具体实现/边界处理有些细节，我写的稍微有点麻烦。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000002;
const int mod=998244353;
int n,m,ans1,ans2;
int a[maxn],b[maxn],qzh[maxn];
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
int sum1=0,sum2=0;
for(int i=1;i<=n;i++) { sum1+=((i*a[i])%mod); sum1%=mod; }
for(int j=1;j<=m;j++) { sum2+=b[j]; sum2%=mod; }
ans1=(sum1*sum2)%mod;
for(int i=1;i<=n;i++) { qzh[i]=qzh[i-1]+a[i]; qzh[i]%=mod; }
for(int i=1;i<=m;i++)
{
int base=i*b[i]; base%=mod;
if(i==1)
{
for(int j=1;j<=n;j++) ans2+=(base*(a[j]*(j/i))%mod)%mod;
continue;
}
int sum=i-1;
for(int k=1;sum<=n;k++)
{
ans2+=((base)*(qzh[min(n,sum+i)]-qzh[sum]+mod)%mod)*k;
ans2%=mod;
sum+=i;
}
}
cout<<((ans1-ans2)+mod)%mod;
return 0;
}
|
比E简单（？
首先观察性质。这种恰好等于一个数的计数问题可以转化为（小于等于的数量
减
小于的数量），所以我们的任务就是计算对于一个序列，有几个区间的逆序对数小于等于一个数。同时我们看到一个性质，就是对于固定的左端点，拓展右端点只会让这个区间里的逆序对变多。所以很显然可以有滑动窗口处理，再用树状数组在这个过程中维护逆序对的数目即可。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000002;
int tree[maxn];
int n,k;
int a[maxn];
void add(int x,int y)
{
while(x<=n)
{
tree[x]+=y;
x+=x&(-x);
}
return;
}
int get(int x)
{
int ans=0;
while(x>0)
{
ans+=tree[x];
x-=x&(-x);
}
return ans;
}
int getans(int now)
{
if(now<0) return 0;
int r=1,cnt=0,tmpans=0; add(a[1],1);
for(int i=1;i<=n;i++)
{
if(i!=1) { cnt-=(get(a[i-1]-1)); add(a[i-1],-1); }
while(r<=(n-1)) { if((cnt+get(n)-get(a[r+1]))<=now) { cnt+=(get(n)-get(a[r+1])); add(a[r+1],1); r++; } else break; }
tmpans+=(r-i+1);
}
return tmpans;
}
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
int ans1=getans(k);
memset(tree,0,sizeof(tree));
int ans2=getans(k-1);
cout<<ans1-ans2;
return 0;
}
|
