hihocoder_offer收割编程练习赛58

时间：2023-02-14 12:20:25

题目链接： https://hihocoder.com/contest/offers58/problems

1.最大的K偏差序列。分析一下数据可以发现，对于连续的2K个数据，只有一种方式可以使结果字典序最大，例如1 2 3 4 5 6 7 8，每4个一组，结果就是5 6 7 8 1 2 3 4。然后不够一组的就先尽可能交换，剩下的元素逆序就可以了。

hihocoder_offer收割编程练习赛58hihocoder_offer收割编程练习赛58
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int MAXN = 100005;
 6 const LL MOD7 = 1e9+7;
 7 int a[105];
 8 int n,K;
 9 
10 void solve()
11 {
12     int t=n/K;
13     int i;
14     for (i=0;;++i)
15     {
16         if (i!=0 && i%K==0) i+=K;
17         if (i >=n || i+K >= n) break;
18         // printf("swap %d %d\n", i, i+K);
19         swap(a[i],a[i+K]);
20     }
21     // printf("i=%d\n", i);
22     int j;
23     if (t%2==0) j=n-1;
24     else j=t*K-1;
25     while (i<j)
26     {
27         swap(a[i],a[j]);
28         ++i;--j;
29     }
30     return ;
31 }
32 
33 int main()
34 {
35 #ifndef ONLINE_JUDGE
36     freopen("test.txt","r",stdin);
37 #endif // ONLINE_JUDGE
38     int Case;
39     scanf("%d%d",&n,&K);
40     for (int i=0;i<n;++i) a[i]=i+1;
41     solve();
42     for (int i=0;i<n;++i)
43     {
44         printf("%d",a[i]);
45         if (i!=n-1) printf(" ");
46     }
47     printf("\n");
48     return 0;
49 }
View Code

2. 孤独的字符。对于每个字符，统计其所在位置左边第一次出现的位置和右边第一次出现的位置。例如hih,对于第一个h，其左边出现的位置为0，右边出现的位置为2，那么这个h对结果的贡献就是，（0-0）*（2-0）+（0-0）+（2-0）+1。第一项是左边和右边的组合，第二项是当前位置和左边的组合，第三项是当前位置和右边的组合，第四项是，当前位置本身。

hihocoder_offer收割编程练习赛58hihocoder_offer收割编程练习赛58
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int MAXN = 100005;
 6 const LL MOD7 = 1e9+7;
 7 
 8 char s[MAXN];
 9 int L[MAXN],R[MAXN];
10 int vis[256];
11 LL ans=0LL;
12 int n;
13 
14 void solve()
15 {
16     n = strlen(s);
17     for (int i=0;i<n;++i)
18     {
19         L[i]=0;
20         R[i]=n-1;
21     }
22     memset(vis,-1,sizeof(vis));
23     for (int i=0;i<n;++i)
24     {
25         L[i]=vis[s[i]]+1;
26         vis[s[i]]=i;
27     }
28     for (int i = 0; i < 256; ++i) vis[i]=n;
29     for (int i=n-1;i>=0;--i)
30     {
31         R[i]=vis[s[i]]-1;
32         vis[s[i]]=i;
33     }
34     ans =0LL;
35     for (int i=0;i<n;++i)
36     {
37         // printf("i=%d L=%d R=%d\n", i,L[i],R[i]);
38         int l=i-L[i];
39         int r = R[i]-i;
40         ans +=(LL)l*(LL)r + l + r + 1;
41     }
42     printf("%lld\n", ans);
43 }
44 
45 int main()
46 {
47 #ifndef ONLINE_JUDGE
48     freopen("test.txt","r",stdin);
49 #endif // ONLINE_JUDGE
50     int Case;
51     scanf("%s",s);
52     solve();
53     return 0;
54 }
View Code

3. 秋天来了。基本的思路是，对于一组关系A B，那么A B之间的大雁所在的高度都要减1。这里采用的做法是，对于一段区间，记录其减少的高度是多少，例如对于关系A B，需要让A+1,A+2,...,B-1这段区间减1，那么我么可以让a[A+1]-1,A[B]+1,然后利用A[0..i]的和来表示，对于i这个位置变化的高度是多少。例如对于x<=A，前缀和A[0..x]为0，不受影响；对于A+1<=x<=B-1，A[0..x]=-1，就是区间中的每个数都会减1；对于x>=B，A[0..x]=0，因为减1被A[B]处的加1抵消了，所以还是没有影响。最后我们计算每个位置的高度变化，加上最大高度就可以了。

需要注意的是，这里的数据包含了1. A==B  2.关系A B 和 B A同时存在的两种特殊的情况。对于第一种情况，直接忽略就可以，对于第2种情况，需要记录是否已经处理过，第二次遇到的时候直接跳过。

hihocoder_offer收割编程练习赛58hihocoder_offer收割编程练习赛58
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int MAXN = 100005;
 6 const LL MOD7 = 1e9+7;
 7 
 8 int n, I, maxH, R;
 9 int a[MAXN];
10 
11 set<tuple<int,int>> st;
12 
13 int main()
14 {
15 #ifndef ONLINE_JUDGE
16     freopen("test.txt","r",stdin);
17 #endif // ONLINE_JUDGE
18     int Case;
19     memset(a,0,sizeof(a));
20     st.clear();
21     scanf("%d%d%d%d", &n,&I,&maxH,&R);
22     int u, v;
23     while (R--)
24     {
25         scanf("%d%d",&u,&v);
26         if (u>v) swap(u,v);
27         tuple<int, int> tmp{u,v};
28         // if (u+1==v) continue;
29         if (st.find(tmp)!=st.end()) continue;
30         if (u==v) continue;
31         a[u+1]-=1;
32         a[v]+=1;
33         st.insert(tmp);
34     }
35     int high=0;
36     for (int i=1;i<=n;++i)
37     {
38         high+=a[i];
39         printf("%d\n",maxH+high);
40     }
41     return 0;
42 }
View Code

 

标签：

相关文章