4个小时A了8题。不得不说，模拟赛的神，现场赛的狗。 不到2小时A了5题简单题，后1个小时A了2道题，字符串和图论，最后A了一道题，数学题。
总体来看，8题是稳拿银牌的，不过考虑到现场赛降智，所以最差铜牌还是有的。 4个小时下来，前7题都很顺利，第8题有点困难，因为队内只有我一个负责数学，其他两个就等我ac，不过最后还是a掉了，估计wa了将近5、6发？
下面按照A题顺序来重温一下。
从n往上继续找第一个能被7整除不能被4整除的数。
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
| ##include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
void solve() {
int \_; scanf("%d",&\_);
while(\_--) {
int n; scanf("%d",&n);
for(int i = n; ;i++) {
if(i % 7 == 0 && i % 4 != 0) {
printf("%d\n",i);
break;
}
}
}
}
signed main() {
solve();
return 0;
}
|
输出删掉除了第一个字符以为的a,e,i,o,u,y的字符串。
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
void solve() {
int \_; cin >> \_;
while(\_--) {
string s;cin >> s;
string t = "";
for(int i = 0;i < (int)s.length(); i++) {
if(i != 0 && (s[i] == 'a' s[i] == 'e' s[i] == 'i' s[i] == 'o' s[i] == 'u' s[i] == 'y')) continue;
t += s[i];
}
cout << t << endl;
}
}
signed main() {
solve();
return 0;
}
|
判断$\sum_{i=l}^rf(i)$的奇偶性。 因为斐波那契数列都是两个奇数，然后一个偶数。
所以考虑n%3的余数。
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
void solve() {
int \_; cin >> \_;
while(\_--) {
string a, b; cin >> a >> b;
int len1 = 0, len2 = 0;
for(int i = 0;i < a.length(); i++) len1 += a[i] - '0';
for(int i = 0;i < b.length(); i++) len2 += b[i] - '0';
if(len1 % 3 == 0 && (len2 % 3 == 2 len2 % 3 == 0)) cout << 0 << endl;
else if(len1 % 3 == 1 && (len2 % 3 == 2 len2 % 3 == 0)) cout << 0 << endl;
else if(len1 % 3 == 2 && len2 % 3 == 1) cout << 0 << endl;
else cout << 1 << endl;
}
}
signed main() {
solve();
return 0;
}
|
考虑删掉每个数之后对波峰的影响。
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
void solve() {
int \_;
cin >> \_;
while (\_--) {
int n;
cin >> n;
vector<int> a(n + 10);
int ans = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
int t = 0;
for (int i = 2; i < n; i++) {
int k = 0;
if (i > 2 && (a[i - 1] > a[i] && a[i - 1] > a[i - 2]) && !(a[i - 1] > a[i - 2] && a[i - 1] > a[i + 1]))
k++;
else if(i > 2 && !(a[i - 1] > a[i] && a[i - 1] > a[i - 2]) && (a[i - 1] > a[i - 2] && a[i - 1] > a[i + 1]))
k--;
if (i + 2 <= n && (a[i + 1] > a[i] && a[i + 1] > a[i + 2]) && !(a[i + 1] > a[i - 1] && a[i + 1] > a[i + 2]))
k++;
else if(i + 2 <= n && !(a[i + 1] > a[i] && a[i + 1] > a[i + 2]) && (a[i + 1] > a[i - 1] && a[i + 1] > a[i + 2]))
k--;
if (a[i] > a[i - 1] && a[i] > a[i + 1]) k++, t++;
ans = max(ans, k);
}
cout << t - ans << endl;
}
}
signed main() {
solve();
return 0;
}
|
排序完数组后，比较每个数的相对位置。 要从后往前比较，这样前面不会对后面产生影响。
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
void solve() {
int \_; cin >> \_;
while(\_--) {
int n; cin >> n;
vector<int> v(n), a(n);
for(int i = 0;i < n; i++) {
cin >> v[i]; a[i] = v[i];
}
sort(v.begin(), v.end());
int ans = 0;
for(int i = n - 1;i >= 0; i--) {
if(a[i] == v[i + ans]) continue;
else ans++;
}
cout << ans << endl;
}
}
signed main() {
solve();
return 0;
}
|
队友写的。 应该拓扑排序？
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| ##include "bits/stdc++.h"
using namespace std;
##define MAXN 2500000
##define MAXM 20000000
##define search(i,y) for(int i = head[y];i;i=edge[i].next)
##define add(u,v,c) {edge[++cnt]={u,v,c,head[u]};head[u]=cnt;}
int head[MAXN],cnt=1;
struct EDGE{
int u,v,c;
int next;
}edge[MAXM];
int used[MAXN];
int used2[MAXN];
vector<int> ans;
signed main(){
int tot;
scanf("%d",&tot);
while(tot--){
ans.clear();
cnt = 1;
int n,m;
scanf("%d%d",&n,&m);
for(int i = 0;i<=n;i++)
used[i] = head[i]=used2[i] = 0;
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b,1);add(b,a,1);
}
queue<int> que;
priority\_queue<int,vector<int>,greater<int>> que2;
int unhappy = 0;
for(int tt = 1;tt<=n;tt++){
if(!used[tt]){
unhappy++;
used[tt] = true;
que.push(tt);que2.push(tt);
}
while(!que.empty()){
int x = que.front();
que.pop();
search(i,x){
int y = edge[i].v;
if(used[y])continue;
used[y] = true;
que.push(y);
}
}
}
while(!que2.empty()){
int x = que2.top();
que2.pop();
ans.push\_back(x);
used2[x] = true;
search(i,x){
int y = edge[i].v;
if(used2[y])continue;
used2[y] = true;
que2.push(y);
}
}
printf("%d\n",unhappy);
for(int i = 0;i<n-1;i++){
printf("%d ",ans[i]);
}
printf("%d\n",ans[n-1]);
}
}
|
队友写的。 马拉车。
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| ##include "bits/stdc++.h"
##define ll long long
using namespace std;
const int maxn=4e6+10;
char s[maxn];
char t[maxn];
char str[2*maxn];
ll len1,len2,p[maxn],ans;
void init()
{
str[0]='$';
str[1]='##';
for(int i=0; i<len1; i++)
{
str[i*2+2]=s[i];
str[i*2+3]='##';
}
len2=len1*2+2;
str[len2]='##';
}
ll manacher()
{
init();
ll id=0,mx=0;
for(ll i=1; i<len2; i++)
{
if(mx>i)
p[i]=min(p[2*id-i],mx-i);
else
p[i]=1;
for(; str[i+p[i]]==str[i-p[i]]; p[i]++);
if(p[i]+i>mx)
{
mx=p[i]+i;
id=i;
}
}
ll ans=0;
for(int i=0;i<len2;i++)
ans+=p[i]/2LL;
return ans;
}
bool reverse(ll l,ll r){
for(ll i=l,j=r;i<=r;i++,j--)
if(s[i]!=t[j])
return false;
return true;
}
int n;
int main()
{
int Case=0;
scanf("%d",&Case);
while(Case--) {
scanf("%s%s",s,t);
ll l=-1;
ll r=-1;
ll flag=0;
len1=strlen(s);
for (ll i = 0; i < len1; ++i) {
if (s[i]!=t[i]){
flag=1;
if (l==-1)
l=i;
r=i;
}
}
ll ans=0;
if (flag){
if (reverse(l,r)){
ans=1;
for (ll i = r+1,j=l-1; i <len1,j>=0; i++,j--) {
if(s[i]==s[j])
ans++;
else
break;
}
}
else
ans=0;
}
else
ans=manacher();
printf("%lld\n",ans);
}
}
|
题意
$原序列a_{1},a_2..a_n$ $x=\sum_{i=1}^ni*a_i$ $y=\sum_{i=1}^ni*a_i^2$
$题目给的是b序列，这两个序列的差别就是b序列是a序列的基础上两个位置交换了。$
$最后问能有多少对交换了位置？$
思路
$设Bx=1*b_1+2*b_2+…i*b_i+…+j*b_j+…+n*b_n$ $假设i和j交换了，则$ $x=1*b_1+…+i*b_j+…+j*b_i+…+n*b_n$ $则Bx-x=i*b_i+j*b_j-i*b_j-j*b_i=(j-i)*(b_j-b_i)$
$同理，设By=…$ $则By-y=(j-i)*(b_j^2-b_i^2)=(j-i)*(b_j-b_i)*(b_j+b_i)$
$我们发现(Bx-x)*(b_i+b_j)=(B_y-y)，除了i和j上的数字我们不知道以为，其他都能算出来。$
$所以(b_i+b_j)是一个定值。$
$所以有以下几种情况：$
- $if\;Bx-x=0\&\&By-y=0，ans=0$
- $if\;Bx-x=0\&\&By-y!=0，ans=C_{每种数字的个数}^2$
- $if\;(By-y)\%(Bx-x)!=0 (By-y)/(Bx-x) <=0，ans=0$
- $else$ $else就是我们最麻烦处理的了。$ $我们知道(b_j+b_i)是一个定值，所以枚举b_i，根据上面几个等式可以算出j，判断b_j=b[j]$ $前面是算出来的，后面j是算出来的，b[j]就是题目给的序列。$
$那么j怎么算呢？$
$Bx-x=(j-i)(b_j-b_i)$
$枚举b_i，算出b_j，j=\frac{Bx-x}{b_j-b_i}+i$ $这题细节很多，要判断b_j-b_i是否=0？j是否>i\&\&j<=n。$
$如果一切成立的话，ans++。$
$最后输出ans。$
$如果暴力O(n^2)铁T，而这个方法就是O(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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
void solve() {
int _; scanf("%d",&_);
while (_--) {
int n; ll x, y; scanf("%d%lld%lld",&n,&x,&y);
vector<int> b(n + 1);
map<int, int> mp;
ll Bx = 0, By = 0;
for(int i = 1;i <= n; i++) {
scanf("%d",&b[i]);
mp[b[i]]++;
Bx += 1ll * i * b[i];
By += 1ll * i * b[i] * b[i];
}
if(Bx == x) {
if(By - y != 0) printf("0\n");
else {
ll ans = 0;
for (auto i : mp) {
ans += 1ll * i.second * (i.second - 1) / 2;
}
printf("%lld\n", ans);
}
}
else if(Bx == x By == y) printf("0\n");
else {
ll tmp = (By - y) / (Bx - x);
if((tmp * (Bx - x) == By - y) && tmp > 0) {
ll ans = 0;
for(int i = 1;i <= n; i++) {
ll aj = tmp - b[i];
if(aj <= 0 (aj - b[i]) == 0 (Bx - x) % (b[i] - aj) != 0) continue;
ll j = (Bx - x) / (aj - b[i]) + i;
if(j <= i j > n) continue;
if(b[j] == aj) ans++;
}
printf("%lld\n",ans);
}
else printf("0\n");
}
}
}
signed main() {
solve();
return 0;
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/22/2019-zhejiang-competition/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！