文章目錄

• T1：A Twisty Movement
• • 題目
  • 題解
  • code
• T2：Add Points
• • 題目
  • 題解
  • code
• T3：The Monster
• • 題目
  • 題解
  • code
• T4：Congruence Equation
• • 題目
  • 題解
  • code

T1：A Twisty Movement

題目

題目

題解

因為$a_i$=$1/2$，于是我們可以確定答案一定是：$[1,1,1,\dots ][2,2,2\dots ][1,1,1\dots ][2,2,2\dots ]$這樣的四段子序列（每一段都允許為空）中第二、三段所在區間翻轉得到

我們可以從左往右做前綴和$pre[i]$表示$[1,i]$出現$1$的個數，后綴和$suf[i]$表示$[i,n]$出現$2$的個數

---

然后我們枚舉二、三段的分界點$k,k\in [1,n+1]$，再設一、二段的分界點為$p,p\in [1,k]$，三、四段的分界點為$q,q\in [k,n+1]$

那么答案為$(pre[p?1])+(suf[p]?suf[k])+(pre[q?1]?pre[k])+(suf[q])$

將式子中括號括起來的當為一個整體
這個式子可以化為：
$(pre[p?1]+suf[p]+pre[q?1]+suf[q])?(suf[k]+pre[k])$
$p\in [1,k],q\in [k,n+1]$

發現對于一個確定的$k$，我們要最大化前面括號的式子
而第一個括號里面的東西可以用線段樹維護下$pre[i?1]+suf[i]$
那么只用枚舉$k$，再兩次區間最大值查詢，更新答案就好了

code

#include <cstdio> #include <iostream> using namespace std; #define MAXN 2005 int n, result; int a[MAXN], pre[MAXN], suf[MAXN], tree[MAXN << 2];void insert ( int t, int l, int r, int id, int val ) {if ( l == r ) {tree[t] = val;return;}int mid = ( l + r ) >> 1;if ( id <= mid )insert ( t << 1, l, mid, id, val );elseinsert ( t << 1 | 1, mid + 1, r, id, val );tree[t] = max ( tree[t << 1], tree[t << 1 | 1] ); }int query ( int t, int l, int r, int L, int R ) {if ( L <= l && r <= R )return tree[t];int mid = ( l + r ) >> 1;int ans = 0;if ( L <= mid )ans = max ( ans, query ( t << 1, l, mid, L, R ) );if ( mid < R )ans = max ( ans, query ( t << 1 | 1, mid + 1, r, L, R ) );return ans; }int main() {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ )scanf ( "%d", &a[i] );for ( int i = 1;i <= n;i ++ )pre[i] = pre[i - 1] + ( a[i] == 1 );for ( int i = n;i >= 1;i -- )suf[i] = suf[i + 1] + ( a[i] == 2 );for ( int i = 1;i <= n + 1;i ++ )insert ( 1, 1, n + 1, i, pre[i - 1] + suf[i] );for ( int i = 1;i <= n + 1;i ++ ) {int tmp1 = query ( 1, 1, n + 1, 1, i ), tmp2 = query ( 1, 1, n + 1, i, n + 1 );result = max ( result, tmp1 + tmp2 - pre[i - 1] - suf[i] ); }printf ( "%d", result );return 0; }

T2：Add Points

題目

題目

題解

這道題實在不知道怎么講，我覺得直接扔一句話就懂了
排完序后兩兩距離的最大公約數

code

#include <cstdio> #include <algorithm> using namespace std; #define MAXN 100005 int n; int x[MAXN];int gcd ( int x, int y ) {if ( ! y )return x;elsereturn gcd ( y, x % y ); }int main() {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ )scanf ( "%d", &x[i] );sort ( x + 1, x + n + 1 );int d = x[2] - x[1];for ( int i = 2;i < n;i ++ ) {int dis = x[i + 1] - x[i];d = gcd ( d, dis );}int result = 0;for ( int i = 1;i < n;i ++ )result += ( x[i + 1] - x[i] ) / d - 1;printf ( "%d", result );return 0; }

T3：The Monster

題目

題目

題解

其實還是有點意思，我認為比$T2$要難一點
首先直接純暴力$2^{5000}$可以直接當場去世了

---

考慮枚舉起點，用$tot$記錄，$($就$+1$，$)$就$?1$，
若$tot==0$，說明匹配成功$result++$

---

對于$?$就麻煩一點了
$tot>0$，表示需要右括號匹配，使$?$為右括號，
因為右括號一定可以改為左括號（期待后面能夠匹配成功），
因此$change++$（$change$為可以修改為左括號的$?$個數）

$tot<0$，$?$只能為左括號，并且不能計入num

---

如果某一個時刻，$tot<0,num>0$，說明可以將之前的右括號改為左括號，則$tot+=2,num??$

剪枝部分：若$tot<0,num=0$，說明此序列當前及以后都不會合法，直接$break$

code

#include <cstdio> #include <cstring> #define MAXN 5005 char s[MAXN]; int result, tot, change;int main() {scanf ( "%s", s );int len = strlen ( s );for ( int i = 0;i < len;i ++ ) {tot = 0, change = 0;for ( int j = i;j < len;j ++ ) {if ( s[j] == '(' )tot ++;else if ( s[j] == ')' ) tot --;else {if ( tot > 0 )tot --, change ++;elsetot ++;}if ( tot < 0 && change > 0 )tot += 2, change --;//°????°μ±3é')'ìá1?μ?-1?ó??à′?ù?óé?'('μ?1±?× if ( tot < 0 && ! change )break;if ( ! tot )result ++;}}printf ( "%d", result ); return 0; }

T4：Congruence Equation

題目

題目

題解

對于這種數論題只想說一句：不康題解：這神馬玩意兒；康完題解：太水了

---

$n?a^n\equiv b(modp)$，加上費馬那一堆人的鬼定理
我們知道第一個乘數$n$的循環節是$p$
而指數$n$的循環節是$\phi (p)$，又因為$p$為質數，所以$\phi (p)=p?1$
綜上$n?a^n$有循環節$p?(p?1)$

---

然后就可以設$n=j?(p?1)+i$，接著開始搞事
$$n?a^n\equiv b(modp)$$
$$(j?(p?1)+i)?a^{j?(p?1)+i}\equiv b(modp)$$
$$(j?p?j+i)?a^i\equiv b(modp)$$
$$(i?j)?a^i\equiv b(modp)$$
$$j\equiv i?\frac{b}{a^i}(modp)$$
然后就可以枚舉$i$解出$j,n$搞到一個最小解，根據循環節算有幾個
$$\frac{x?minn}{p?(p?1)}$$

code

#include <cstdio> #define int long long int a, b, p, x, result;int qkpow ( int x, int y ) {int ans = 1;while ( y ) {if ( y & 1 )ans = ans * x % p;x = x * x % p;y >>= 1;}return ans; }signed main() {scanf ( "%lld %lld %lld %lld", &a, &b, &p, &x );for ( int i = 1;i < p;i ++ ) {int j = ( i - b * qkpow ( qkpow ( a, i ), p - 2 ) % p + p ) % p;int minx = j * ( p - 1 ) + i;if ( minx <= x )result += ( x - minx ) / ( p * ( p - 1 ) ) + 1;}printf ( "%lld", result );return 0; }

總結

以上是生活随笔為你收集整理的[2.7]【CF933A】A Twisty Movement【CF926B】Add Points【CF917A】The Monster【CF919E】Congruence Equation的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。