Educational Codeforces Round 70 (Rated for Div. 2)
A. You Are Given Two Binary Strings...
-
思路：水题
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
int t, len1, len2, pos1, pos2, ans;
string a, b;
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t -- ){
ans = 0;
cin >> a >> b;
len1 = a.length(), len2 = b.length();
for (int i = len2 - 1; i >= 0; i -- ){
if (b[i] == '1'){
pos2 = i;
break;
}
}
for (int i = len1 - (len2 - pos2); i >= 0; i -- ){
if (a[i] == '1'){
pos1 = i;
break;
}
}
cout << (len1 - pos1) - (len2 - pos2) << "
";
}
return 0;
}
B. You Are Given a Decimal String...
-
思路：floyd最短路
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
const int N = 10;
const int INF = 0x3f3f3f3f;
int len, ans;
string s;
bool flag;
int dp[N][N];
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
len = s.length();
for (int x = 0; x < N; x ++ ){
for (int y = 0; y < N; y ++ ){
memset(dp, INF, sizeof(dp));
ans = 0;
flag = true;
for (int i = 0; i < N; i ++ ){
dp[i][(i + x) % 10] = 1;
dp[i][(i + y) % 10] = 1;
}
for (int k = 0; k < N; k ++ )
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
/* for (int i = 0; i < N; i ++ ){
for (int j = 0; j < N; j ++ )
cout << dp[i][j] << " ";
cout << "
";
} */
for (int i = 1; i < len; i ++ ){
int l = s[i - 1] - '0', r = s[i] - '0';
if (dp[l][r] == INF){
flag = false;
break;
}
ans += dp[l][r] - 1;
}
if (flag)
cout << ans << " ";
else
cout << -1 << " ";
}
cout << "
";
}
return 0;
}
D. Print a 1337-string...（赛后补）
-
思路：构造出类似于133/77...77/33...33/7这样的串
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
int t, n, cnt;
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t -- ){
cnt = 1;
cin >> n;
cout << "133";
while (cnt * (cnt - 1) / 2 <= n)
cnt ++ ;
cnt -- ;
for (int i = 1; i <= n - cnt * (cnt - 1) / 2; i ++ )
cout << "7";
for (int i = 1; i <= cnt - 2; i ++ )
cout << "3";
cout << "7
";
}
return 0;
}
E. You Are Given Some Strings...
-
思路：正着反着分别跑一次AC自动机
-
AC代码
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mult_mod(ll x, ll y, ll mod){
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll pow_mod(ll a, ll b, ll p){
ll res = 1;
while (b){
if (b & 1)
res = mult_mod(res, a, p);
a = mult_mod(a, a, p);
b >>= 1;
}
return res % p;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
const int N = 2e5 + 10;
struct Trie{
int next[N][26], fail[N], end[N], res[N];
int tot;
int newnode(){
int now = ++ tot;
end[now] = 0;
return now;
}
void init(){
tot = 0;
newnode();
}
void insert(string buf){
int len = buf.length();
int now = 1;
for (int i = 0; i < len; i ++ ){
if (!next[now][buf[i] - 'a'])
next[now][buf[i] - 'a'] = newnode();
now = next[now][buf[i] - 'a'];
}
end[now] ++ ;
}
void build(){
queue<int> q;
for (int i = 0; i < 26; i ++ ){
if (!next[1][i])
next[1][i] = 1;
else{
fail[next[1][i]] = 1;
q.push(next[1][i]);
}
}
while(!q.empty()){
int now = q.front();
q.pop();
end[now] += end[fail[now]];
for (int i = 0; i < 26; i ++ ){
if (!next[now][i])
next[now][i] = next[fail[now]][i];
else{
fail[next[now][i]] = next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
}ac1, ac2;
int n;
ll ans;
string s, t;
int main(){
#ifndef ONLINE_JUDGE
freopen("my_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s >> n;
int len = s.length();
ac1.init(), ac2.init();
for (int i = 1; i <= n; i ++ ){
cin >> t;
// cout << t << " ";
ac1.insert(t);
reverse(t.begin(), t.end());
// cout << t << " ";
ac2.insert(t);
}
ac1.build(), ac2.build();
for (int i = 0, now = 1; i < len; i ++ ){
ac1.res[i] = ac1.end[ac1.next[now][s[i] - 'a']];
now = ac1.next[now][s[i] - 'a'];
}
for (int i = len - 1, now = 1; i >= 0; i -- ){
ac2.res[i] = ac2.end[ac2.next[now][s[i] - 'a']];
now = ac2.next[now][s[i] - 'a'];
}
for (int i = 0; i < len - 1; i ++ )
ans += 1ll * ac1.res[i] * ac2.res[i + 1];
cout << ans << "
";
return 0;
}