题意：
给你
a
a
a个一块钱的硬币和
b
b
b个两块钱的硬币,求最大不能被凑出来的正整数
思路：
-
如果 a a a为 0 0 0,说明 1 1 1我们无论无何也凑不出来
-
如果 a a a存在,说明 [ 1 , a + 2 ∗ b ] [1,a+2*b] [1,a+2∗b]中的任何一个正整数都可以凑出来,答案即为 a + 2 b + 1 a+2b+1 a+2b+1
时间复杂度： O t Ot Ot
#define cf int _; cin>> _; while(_--)
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ; // mod = 998244353 ;
int n , m ;
int a[N] ;
signed main()
{
cf
{
int a , b ;
cin >> a >> b ;
if(a >= 1)
cout << a + 2 * b + 1 << '\n' ;
else
{
puts("1") ;
}
}
return 0 ;
}
题意：
给你
n
n
n个数的数组,每次你可以任选一个最大的数
a
[
i
]
a[i]
a[i],使其减一
但是不能连续选 2 2 2个下标相同的数,求是否可以都减为 0 0 0
思路：
- 显然当最大值减去次大值
>
=
2
>=2
>=2
说明无论无何也不可以都减为 0 0 0
在证明其他情况一定可以的充要性
- 我们假设最大值为
d
1
d1
d1,次大值为
d
2
d2
d2
我们先减去 d 1 d1 d1,在减 d 2 d2 d2,然后不断重复
在减去的过程中,如果出现了与其他数相等的情况
就依次减去其他相等的数,这样子一定可以保证都可以减为 0 0 0
时间复杂度： O n l o g n Onlogn Onlogn
#define fer(i,a,b) for(int i = a ; i <= b ; ++ i)
#define cf int _; cin>> _; while(_--)
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ; // mod = 998244353 ;
int n , m ;
int a[N] ;
signed main()
{
cf
{
cin >> n ;
fer(i,1,n) cin >> a[i] ;
sort(a + 1 , a + 1 + n) ;
if(n == 1)
{
cout << (a[1] == 1 ? "YES" : "NO") << '\n' ;
}
else
{
cout << (a[n] - a[n - 1] >= 2 ? "NO" : "YES") << "\n" ;
}
}
return 0 ;
}
题意：
给你一个字符串,求将其变为
a
a
c
c
x
x
f
f
e
e
.
.
.
.
.
aaccxxffee.....
aaccxxffee.....等任意字母都连续出现偶数个数的情况下你需要删除字母个数的最小值
n < = 2 e 5 n <= 2e5 n<=2e5
思路：
直接求不好求,不如换个思路
- 原题等价于n-最大任意字母都连续出现偶数情况下的字符串长度
求最大长度遍历一遍即可
时间复杂度： O n On On
inline void de(auto x) {cout << x << "\n" ;}
#define cf int _; cin>> _; while(_--)
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ; // mod = 998244353 ;
int n , m ;
int a[N] ;
char s[N] ;
signed main()
{
cf
{
cin >> s + 1 ;
n = strlen(s + 1) ;
bitset<200> st ;
st[s[1]] = 1 ;
int res = 0 ;
for(int i = 2 ; i <= n ; i ++)
{
if(st[s[i]])
{
res += 2 ;
st.reset() ;
}
else
{
st[s[i]] = 1 ;
}
}
de(n - res) ;
}
return 0 ;
}
题意：
给你一个
n
n
n个数的数组
你可以删去任意数组前缀或者任意数组后缀
求删去之后使剩下的子数组的乘积最大
输出前缀删除的个数以及后缀删去的个数
题目规定空的子数组[]的乘积为1
n < = 2 e 5 , ∣ a [ i ] ∣ < = 2 n <= 2e5 , |a[i]|<=2 n<=2e5,∣a[i]∣<=2
思路：
一道比较考验码力 的题,不知道有没有更简单的方法
首先题目定义了空的子数组[]的乘积为
1
1
1
说明最后剩下的子数组一定不能出现
0
0
0
根据此性质我们可以把数组分为
0.....0......0......0.....0
0 ..... 0 ...... 0......0.....0
0.....0......0......0.....0
特殊定义
a
[
0
]
=
0
,
a
[
n
+
1
]
=
0
a[0] = 0 , a[n + 1] = 0
a[0]=0,a[n+1]=0
对每一个
0.......0
0.......0
0.......0
可以分
2
2
2种情况讨论
- 情况 1 1 1,区间负数个数为偶数,说明此区间乘积必定为正,更新一下最大值
- 情况 2 2 2,区间负数个数为奇数,二分找到这个区间的第一个负数和最后一个负数的下标,更新一下最大值
时间复杂度： O n l o g n Onlogn Onlogn
#define fer(i,a,b) for(int i = a ; i <= b ; ++ i)
#define lb lower_bound
#define ub upper_bound
inline void de2(auto a , auto b) {cout << a << " " << b << "\n" ;}
#define cf int _; cin>> _; while(_--)
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ; // mod = 998244353 ;
int n , m ;
int a[N] ;
int s[N] ; // s[i]表示[1,i]中负数的个数
int ss[N] ; // ss[i]表示[1,i]中a[i]绝对值=2的个数
int res , ll , rr ;
void get(int l , int r)
{
int x = s[r] - s[l - 1] ;
int sum = ss[r] - ss[l - 1] ;
if(sum > res && x % 2 == 0)
{
res = sum ;
ll = l - 1 , rr = n - r ;
}
}
signed main()
{
cf
{
cin >> n ;
vector<int> v ;
fer(i,1,n) cin >> a[i] , s[i] = s[i - 1] + (a[i] < 0) , ss[i] = ss[i - 1] + (abs(a[i]) == 2) ;
a[0] = 0 , a[n + 1] = 0 ;
fer(i,0,n+1)
if(a[i] == 0)
v.push_back(i) ;
multiset<int> q ; // set里面放所有负数的下标
fer(i,1,n)
if(a[i] < 0)
q.insert(i) ;
res = -1e9 ;
ll = 1 , rr = n - 1 ;
for(int i = 0 ; i + 1 < v.size() ; i ++)
{
int l = v[i] + 1 , r = v[i + 1] - 1 ;
int x = s[r] - s[l - 1] ;
if(x % 2 == 0)
{
get(l,r) ;
}
else
{
auto it = q.lb(l) ;
get(*it + 1 , r) ;
it = q.ub(r) ;
-- it ;
get(l , *it - 1) ;
}
}
de2(ll , rr) ;
}
return 0 ;
}
题意：
给你
n
∗
n
n*n
n∗n的数组,你可以进行以下 *** 作任意次
- 将第一行移动到最后一行
- 将最后一行移动到第一行
- 将第一列移动到最后一列
- 将最后一列移动到第一列
问你怎么 *** 作使得
该数组与另外一个n*n的数组(主对角线都是1,其余全为0)不同的数的个数最小
思路：
假设此数组
1
1
1的总个数为
s
u
m
sum
sum
与另外一个数组重合的
1
1
1的个数为
r
e
s
res
res
那么
- 主对角线其余地方不同的数的个数为 s u m − r e s sum-res sum−res
- 主对角线上不同的数的个数为 n − r e s n-res n−res
答案即为
s
u
m
+
n
−
2
∗
r
e
s
sum + n - 2 * res
sum+n−2∗res
因为要最小化结果,
s
u
m
,
n
sum,n
sum,n都为常数
等价于求
r
e
s
res
res的最大值
我们可以枚举向右的偏移量
i
i
i和第
j
j
j行
同时更新
r
e
s
res
res的最大值,即为
s
[
j
]
[
(
i
+
j
)
%
n
]
=
=
1
s[j][(i + j) \% n] == 1
s[j][(i+j)%n]==1的总个数
时间复杂度： O n 2 On^2 On2
#define fer(i,a,b) for(int i = a ; i <= b ; ++ i)
#define cf int _; cin>> _; while(_--)
inline void de(auto x) {cout << x << "\n" ;}
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ; // mod = 998244353 ;
int n , m ;
char s[M][M] ;
signed main()
{
cf
{
cin >> n ;
int sum = 0 ;
fer(i,0,n-1)
fer(j,0,n-1)
{
cin >> s[i][j] ;
if(s[i][j] == '1') sum ++ ;
}
int res = 0 ;
fer(i,0,n-1)
{
int k = 0 ;
fer(j,0,n-1)
{
if(s[j][(i + j) % n] == '1')
k ++ ;
}
res = max(res , k ) ;
}
de(n + sum - 2 * res) ;
}
return 0 ;
}
题意：
给你一个只包含
+
+
+或
−
-
−的字符串
你可以将连续的2个负号变成正号
求有多个子字符串满足
+
+
+的数量=
−
-
−的数量
思路：
首先我们假设有a个负号,b个正号
将连续的2个负号变成正号
等价于
-
a − 2 k = b + k a-2k=b+k a−2k=b+k
-
a − b = 3 k a-b=3k a−b=3k
也就是求有多少个
-
( a − b ) % 3 = = 0 (a-b) \% 3 == 0 (a−b)%3==0
-
并且 a > = b a >= b a>=b
我们假设正号为
−
1
-1
−1,负号为
+
1
+1
+1
s
[
i
]
s[i]
s[i]数组表示
[
1
,
i
]
[1,i]
[1,i]这个区间的和
等价于求有多少个
[
l
,
r
]
[l,r]
[l,r]
满足
-
( s [ r ] − s [ l − 1 ] ) % 3 = = 0 (s[r]-s[l-1]) \% 3 == 0 (s[r]−s[l−1])%3==0
-
并且 s [ r ] > = s [ l − 1 ] s[r] >= s[l-1] s[r]>=s[l−1]
考虑
-
( s [ r ] − s [ l − 1 ] ) % 3 = = 0 (s[r]-s[l-1]) \% 3 == 0 (s[r]−s[l−1])%3==0
开三个数组即可,因为任何数 % 3 \%3 %3都只有三个取值 -
并且 s [ r ] > = s [ l − 1 ] s[r] >= s[l-1] s[r]>=s[l−1]
树状数组即可，因为树状数组可以动态统计小于等于这个数的情况下,什么什么的个数,参考逆序对的求法
在求的过程中,会有负数出现,所以还需离散化
时间复杂度： O n l o g n Onlogn Onlogn
#define fer(i,a,b) for(int i = a ; i <= b ; ++ i)
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define int long long
#define pb push_back
#define cf int _; cin>> _; while(_--)
inline void de(auto x) {cout << x << "\n" ;}
inline int mo(int a , int b) {return a = (a % b + b) % b ;}
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ; // mod = 998244353 ;
int n , m ;
int a[N] , s[N] ;
char g[N] ;
int tr[4][N] ;
int d ;
int lowbit(int x)
{
return x & -x ;
}
int sum(int x)
{
long long res = 0 ;
for(int i = x ; i ; i -= lowbit(i)) res += tr[d][i] ;
return res;
}
void add(int x , int c)
{
for(int i = x ; i <= n + 1 ; i += lowbit(i)) tr[d][i] += c ;
}
vector<int> q ;
int get(int x)
{
return lb(all(q) , x ) - q.begin() + 1 ;
}
signed main()
{
cf
{
cin >> n >> g + 1 ;
fer(i,1,n)
{
s[i] = s[i - 1] + (g[i] == '-' ? 1 : -1) ;
}
fer(i,0,2)
fer(j,0,n + 10)
tr[i][j] = 0 ;
q.clear() ;
fer(i,0,n) q.pb(s[i]) ;
sort(all(q)) ;
q.erase( unique(all(q)) , q.end() ) ;
//fer(i,0,n) de2(s[i] , get(s[i])) ;
int res = 0 ;
fer(i,0,n)
{
d = mo(s[i] , 3) ;
res += sum(get(s[i])) ;
add(get(s[i]), 1) ;
}
de(res) ;
}
return 0 ;
}
顺便添上
F
1
F1
F1的代码
时间复杂度：
O
n
2
On^2
On2
#define cf int _; cin>> _; while(_--)
inline void de(auto x) {cout << x << "\n" ;}
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ; // mod = 998244353 ;
int n , m ;
int a[N] ;
char s[N] ;
signed main()
{
cf
{
cin >> n >> s + 1 ;
int res = 0 ;
for(int i = 1 ; i <= n ; i ++)
{
int s1 = 0 , s0 = 0 ;
for(int j = i ; j <= n ; j ++)
{
if(s[j] == '-') s0 ++ ;
else s1 ++ ;
if(s0 >= s1 && (s0 - s1) % 3 == 0)
res ++ ;
}
}
de(res) ;
}
return 0 ;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）