10.13OI集训营普及组第五场题解
T1 复读
考察基础的字符串匹配，
表示当前匹配到 
字符串的第 位，
表示当前匹配到 
字符串的第 位，两两比较，如果 等于 )
，说明一遍已经复制完了，从零开始重新匹配（题解中用取模表示这一效果）
#include<bits/stdc++.h>
using namespace std;
string s, t;
int main() {
int T;
cin >> T;
while(T--) {
bool flag = 0;
cin >> s >> t;
for(int i = 0, j = 0; i < s.size(); ++i) {
if(s[i] != t[j]) flag = 1;
++j; j %= t.size();
}
if(flag) puts("NO"); else puts("YES");
}
}
T2 学习乘法
注意到本题的乘法都是最多两位数相乘，所以我们只需要将读入的#include<cstdio>
int ans(int a, int b){
int a1 = a/10, a2 = a%10, b1 = b/10, b2 = b%10;
return a1 * b1 + a1 * b2 + a2 * b1 + a2 * b2;
}
int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d", ans(a, b));
} T3 求和
如果此时，考虑枚举每个
这是因为对于每个
而这样的区间共有
去重后怎么做呢？考虑换一种方式解释去重：我们只计算每个数第一次出现时产生的贡献。
设
那么在这种方式下，
计算
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
const int mod = 1e9 + 7;
int n, a[N];
map<int,int>mp;
int l[N], r[N];
int main() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
mp[a[i]] = 1;
}
mp.clear();
for(int i = 1; i <= n; ++i) {
l[i] = mp[a[i]] + 1;
mp[a[i]] = i;
}
mp.clear();
for(int i = n; i; --i) {
if(!mp.count(a[i])) {
r[i] = n;
} else r[i] = mp[a[i]] - 1;
mp[a[i]] = i;
}
ll ans = 0;
for(int i = 1; i <= n; ++i) {
ans += 1ll * a[i] * (i - l[i] + 1) % mod * (n - i + 1) % mod;
ans %= mod;
}
cout << ans << endl;
} T4 点集操作
可以使用模拟暴力拿到一些分，正解还是较思维。正解：
发现在一个单向链上，只需要让链头的两个点进行一次操作就可以将整个链变成两个点。
所以每次操作可以在一条所含点数超过
由上面操作的特殊性可以知道所有入度为
统计这些点个数即可。
复杂度：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,m,x[MAXN<<1],y[MAXN<<1],in[MAXN];
int head[MAXN],num,ans;
bool b[MAXN],vis[MAXN];
vector<int>v;
queue<int>q;
struct node{
int to,next;
}e[MAXN<<1];
void add(int u,int v){
e[++num].to=v;
e[num].next=head[u];
head[u]=num;
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;++i){
cin >> x[i] >> y[i];
add(x[i],y[i]);
in[y[i]]++;//统计入度
}
for(int i=1;i<=n;++i){
if(!in[i]){//如果入度为零
v.push_back(i);//记录入度为零的点
ans++;//这些点肯定不能被删去
}
}
for(int i=1;i<=m;++i){
if(in[x[i]])b[y[i]]=1;//将入边对应点入度大于零的点标记，这些点都不行
}
for(int i=0;i<v.size();++i){//最外层
for(int j=head[v[i]];j;j=e[j].next){//第二层
if(!b[e[j].to]){//若第二层的点的**所有**入边对应点入度等于零（有些点既在第二层又在其它层）
b[e[j].to]=1;
ans++;//这些点虽然会被删除，但是他们可以充当新点，相当于保留
}
}
}
cout << ans;
return 0;
} 
地平线公司福利 418人发布
