题目链接
A 00:01
B 00:08
C 00:22
D 00:41
E 01:00
F --:--
A. Wrong Subtraction
如果一个数最后一位大于0则减1,否则除10
这部操作执行k次
int n = read(), k = read();
while(k --){
if(n % 10){
n --;
}else{
n /= 10;
}
}
cout << n << endl;
B. Two-gram
找一个长度为2的字串,是这个字符串出现次数最多的字串
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define _ 0
#define eps 1e-9
#define endl '\n'
#define gcd __gcd
#define pi acos(-1)
#define ll long long
#define LL long long
#define IDX(x) (x - 'A')
#define idx(x) (x - 'a')
#define idz(x) (x - '0')
#define ld long double
#define lowebit(x) (x&(-x))
#define rint register int
#define Len(x) (int)(x).size()
#define all(s) (s).begin(), (s).end()
//char buf[1 << 23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
#define int ll
inline int read()
{
register int x = 0, f = 1, ch = getchar();
while( !isdigit(ch) ){if(ch == '-') f = -1; ch = getchar();}
while( isdigit(ch) ){x = (x << 1) + (x << 3) + ch - 48; ch = getchar();}
return x * f;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
clock_t c1ockck = clock();
// ..........................................................
int n; cin >> n;
string s; cin >> s;
int ans = 0;
string p = "";
for(int i = 0 ; i + 1 < Len(s) ; i ++){
int sum = 0;
for(int j = i ; j + 1 < Len(s) ; j ++){
if(s[j] == s[i] && s[i + 1] == s[j + 1]){
sum ++;
}
}
if(ans < sum){
ans = sum;
p = s[i];
p = p + s[i + 1];
}
}
cout << p << endl;
// ..........................................................
cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
return ~~(0^_^0);
}
C. Less or Equal
找出一个x使序列里面恰好有k个数小于等于x
首先直接sort看第k个元素等不等于第k+1个元素,如果等于肯定找不出来
否则输出第k个
但是如果k为0的话那就看第一个元素,如果大于1则输出1~第一个元素-1,否则因为x不能等于零,所以也找不到x
int n = read(), k = read();
for(int i = 1 ; i <= n ; i ++) a.push_back(read());
a.push_back(1e10);
sort(all(a));
if(!k && a[0] == 1) cout << -1 << endl;
else if(!k) cout << a[0] - 1 << endl;
else if( a[k - 1] == a[k]) cout << -1 << endl;
else cout << a[k - 1] << endl;
D. Divide by three, multiply by two
个人感觉写了一个假算法,但是能在cf上AC应该就没有问题
枚举第一个元素,就是看看如果他是3的倍数且他除3存在,下一个就是他除3否则下一个就是他乘2
int n = read();
for(int i = 1 ; i <= n ; i ++) a.push_back(read());
for(auto x : a) m[x] ++;
for(auto x : a){
map<int, int> tmp = m;
vector<int> b;
m[x] --;
b.push_back(x);
bool flag = false;
for(int i = 1 ; i < n ; i ++){
b.push_back(0);
if(b[i - 1] % 3 == 0){
b[i] = b[i - 1] / 3;
if(m[b[i]]){
m[b[i]]--;
continue;
}
}
b[i] = b[i - 1] * 2;
if(m[b[i]]){
m[b[i]]--;
continue;
}
//puts("x");
flag = true;
break;
}
if(!flag){
for(auto y : b) cout << y << " ";
cout << endl;
return 0;
}
m = tmp;
}
E. Cyclic Components
给定一个图,找一下这个图里面有多少简单环(只存在一个环的联通图,并且不出现分支)
如果每次都是在找是否存在环,那么这道题其实很难写
因此需要遍历所有联通图,寻找这个联通图的每个点的最大度数和最小度数
如果都等于2那么这个联通图就是简单环
证明省略...........
pair<int, int> dfs(int u){
int mi, ma = mi = Len(a[u]);
if(vis[u]) return make_pair(mi,ma);
vis[u] = 1;
for(auto x : a[u]){
auto y = dfs(x);
mi = min(y.first, mi);
ma = max(y.second, ma);
}
return make_pair(mi, ma);
}
int n = read(), m = read();
for(int i = 1 ; i<= m ; i ++){
int u = read(), v = read();
a[u].push_back(v);
a[v].push_back(u);
}
int ans = 0;
for(int i = 1 ; i <= n ; i ++){
if(vis[i]) continue;
auto x = dfs(i);
if(x.first == 2 && x.second == 2) ans ++;
}
cout << ans << endl;
F. Consecutive Subsequence
这道题别看写了一个小时wa了19次都没有出来,只是算错复杂度了,导致一直没有正确的debug
我第一次写的代码评价复杂度确实是nlogn的,但是在最坏情况下比如只有两个数每个数出现次数都是\frac{n}{2},这样的话复杂度就是\frac{nlogn}{4}
思路一
枚举每一个没有访问过的元素,并且这个元素的下标也是没有访问过的
然后去查找需要出现的下一个元素是否存在,
存在的话就继续上一步
int n = read();
for(int i = 1 ; i <= n ; i ++) a.push_back(read());
for(auto x : a){
b.push_back(x);
b.push_back(x + 1);
}
sort(all(b));
b.erase(unique(all(b)), b.end());
for(auto& x: a){
x = lower_bound(all(b), x) - b.begin() + 1;
}
for(int i = 0 ; i < n ; i ++) c[a[i]].push_back(i + 1);
int l = 0, r = n - 1;
vector<int> ans;
for(int i = 0 ; i < n ; i ++){
if(vis[i] || v[a[i]]) continue;
vector<int> tmp;
int nex = a[i] + 1, up = i + 1;
tmp.push_back(i + 1);
v[a[i]] = 1;
while(Len(c[nex])){
if(!Len(c[nex])) break;
int x = lower_bound(all(c[nex]), up) - c[nex].begin();
if(x + c[nex].begin() != c[nex].end()){
vis[c[nex][x]-1] = 1;
tmp.push_back(c[nex][x]);
up = c[nex][x];
nex ++;
continue;
}
break;
}
if(Len(tmp) > Len(ans)) ans = tmp;
}
cout << Len(ans) << endl;
for(auto x : ans) cout << x << " " ;
思路二
对于每一个元素我直接二分它的下一个元素,并且让下一个元素的长度看看需不需要加上当前元素的长度,如果需要就记录前驱,并更新下一个元素的长度
记录最长的长度和最长的长度出现的最后一个元素
倒叙输出所有元素
void print(int u){
if(up[u] != -1) dfs(up[u]);
cout << u + 1 << " ";
}
memset(up, -1, sizeof up);
int n = read();
for(int i = 1 ; i <= n ; i ++) a.push_back(read());
for(auto x : a){
b.push_back(x);
b.push_back(x + 1);
}
sort(all(b));b.erase(unique(all(b)), b.end());
for(auto& x: a) x = lower_bound(all(b), x) - b.begin() + 1;
for(int i = 0 ; i < n ; i ++) c[a[i]].push_back(i), vis[i] = 1;
int len = 1, nex = 0;
for(int i = 0 ; i < n ; i ++){
int x = lower_bound(all(c[a[i] + 1]), i) - c[a[i] + 1].begin();
if(x == Len(c[a[i] + 1])) continue;
if(vis[c[a[i] + 1][x]] < vis[i] + 1){
vis[c[a[i] + 1][x]] = vis[i] + 1;
up[c[a[i] + 1][x]] = i;
}
if(vis[c[a[i] + 1][x]] > len){
len = vis[c[a[i] + 1][x]];
nex = c[a[i] + 1][x];
}
}
cout << len << endl;
print(nex);