第一周
C. Queries for the Array
思路
本质上就是模拟操作，但是需要许多细节判断
- 对于操作 "+" ,加上一个数，保证如果此时pos大于2,保证了一定会有可以变为无序，且之前的pos的判断也会继承
- 对于存在 ”-“，需要维护上一个有序判断的最后一位
- 对于"0" ,需要判断此时长度，如果小于2，就错，否则判断此时是否有机会无序，可以的话，将此时有序的机会为0
- 对于"1",如果此时判断为可以，则到 pre+1 到 pos的无序机会都消除，pre = pos。注意这里不可以是pre，因为
小结
原来写的没有考虑好回滚这件事，判断出现了错误。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <array>
using namespace std;
const int N = 200010;
array<int,2> a[N];
void solve()
{
string s;
cin>>s;
int pos =0;
int pre =0;
a[0] = {0,1};
int flag = 1;
for(auto op:s)
{
if(op=='+')
{
pos++;
a[pos] = a[pos-1];
if(pos>=2) a[pos][0] =1;
}
else if(op=='-')
{
pos--;
pre= min(pos,pre);
}
else if(op=='1')
{
if(pos<2) continue;
if(!a[pos][1]) flag = 0;
else {
while(pre<=pos)
{
a[pre][0] =0;
pre
}
pre = pos;
}
}
else if(op=='0')
{
if(pos<2)
{
flag =0;
continue;
}
if(!a[pos][0]) flag =0;
else a[pos][1] =0;
}
}
if(flag) cout<<"YES\n";
else cout<<"NO\n";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
President
思路
//状态方程 类似背包，dp[n][m],为前n种中，大于等于m位的最小值
//将每个区域划分为取或不取，则有 dp[n][m] = min(dp[n-1][m],d[n-1][m-z[i]]+w[i])
//按01背包的空间优化或就为 dp[m] = min(dp[m],dp[m-z[i]]+w[i])
小结
类型01背包的做法。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <array>
using namespace std;
const int N = 200010;
typedef long long ll;
ll dp[N];
int x[N];
int y[N];
int z[N];
int n;
void solve()
{
cin>>n;
int sumz=0;
for(int i =1;i<=n;i++)
{
cin>>x[i]>>y[i]>>z[i];
sumz+=z[i];
}
memset(dp,0x3f3f3f3f,sizeof dp );
dp[0] =0;
for(int i = 1;i<=n;i++)
{
int ans = max(0,(y[i] - ((y[i]+x[i])/2)));
for(int j =sumz;j>=z[i];j--)
{
dp[j] =min(dp[j],dp[j-z[i]]+ans);
}
}
long long res =2e18;
for(int i = (sumz)/2+1;i<=sumz;i++) res =min(res,dp[i]);
cout<<res<<"\n";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
t =1;
while(t--)
{
solve();
}
return 0;
}
C. Sum on Subarrays
https://codeforces.com/contest/1809/problem/C
思路
要求构造一个长度为n的序列，要求有k个子段和为正数。
先考虑子段和的数量，如果长度为 n 那么子段数量为
则如果有k个正数就会至少有 个 子段和为正数。
-
如果我们要求的k刚好符合 （n*（n+1））/2的话，那就直接构造几个正数就可以。剩下就构造出绝对值大于所有正数的和的负数就行。
-
可是k ！= (m*(m+1)/2) 的话，我们就找到 k>(m *(m+1)/2)中m的最大值。
我们可以发现 （m+1）* （m+2)/2 - ( m+1)*(m)/2 == m+1。，减去自己就有m个也就是说有m个数
恰好， k - (m*(m+1)/2) >0, k<( (m+2)*(m+1)/2),说明剩下没有构造的数是可以通过构造一个负数来获得这剩下的数的
例子： 3，4
可以有-59，30，30
4 - 2*(2+1)/2 = 1
那么我们就构造一个 负数 -1*( m - 1 +1)*30+1
这个大概思路也可以用在下面ice那道题
小结
连续子段数量都是用
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50;
int a[N];
int t;
int n;
int k;
int check(int x)
{
int ans =0;
for(int i = 1;i<=n;i++)
{
if(k>=(i*(i+1)/2)) ans = i;
}
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>t;
while(t--)
{
cin>>n>>k;
int ans = check(k);
if(k == ans*(ans+1)/2)
{
for(int i = n;i>n-ans;i--) a[i] = 30;
for(int i = 1;i<=n-ans;i++) a[i] = -901;
for(int i = 1;i<=n;i++) cout<<a[i]<<" ";
cout<<"\n";
}
else
{
for(int i =n;i>n-ans;i--) a[i] = 30;
k = k-(ans*(ans+1)/2);
a[n-ans] = ((-1)*(1+(ans-k))*30) +1;
for(int i = 1;i<n-ans;i++)
{
a[i] = -901;
}
for(int i =1;i<=n;i++)
{
cout<<a[i]<<" ";
}
cout<<"\n";
}
}
return 0;
}
D - Three Days Ago
https://atcoder.jp/contests/abc295/tasks/abc295_d?lang=en
思路
问有多少子区间中，每个字母都出现偶数次。
这类问子区间的问题，可以尝试着往前缀和的方向想。题目中的重点在于每个字母都出现 偶数次 显然总结统计是很吃力麻烦的。
但是注意到我们只需要知道区间内字母都出现偶数就行了，那么我们可以用 XOR 来解决。用一个数组统计每个数字出现次数的奇偶性，
用前缀异或维护，如果之前出现过相同的数组l,并设当前的数组为r，则说明，在l到r之间的所有字母都出现了偶数次。
比如
0 : 00000
1 : 00100
2 : 01100
.......
n : 00100
其中1和n相同说明1到n中加上的 这(n-1) 字母中每种字母的出现次数都为偶数，因为一个数xor自己就是0
小结
关于异或的性质。
/*
交换律： p^q == q^p;
结合律： p^(q^r) == (p^q)^r
恒等律： p^0 == p
归零律： p^p == 0
自反 p^p^q == 0^q = q，
很多题会用到p^p==0， 的性质来判断奇偶性质
可以前缀异或自然也可以前缀差分
*/
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int flag=0;
vector<long long> bk(1024,0);//用1024代表0到9位，方便异或
bk[0]++;//这里需要0出现一次，可以理解为flag初始化出现一次
long long res=0;
for(auto &nx : s){
flag^=(1<<(nx-'0'));
res+=bk[flag];
bk[flag]++;
}
cout << res << "\n";
return 0;
}
D. Co-growing Sequence
https://codeforces.com/problemset/problem/1547/D
思路
本题重点在于怎么找到当前n的最小b[i], a[i]^b[i] &(a[i-1]^b[i-1]) == a[i-1] 最小的值。既然是涉及位运算，那么我们就从二进制的形式来看。 如果要使得and 操作后为原来的数，而且保证是最小的。
那么在二进制中我们用贪心的策略
二进制中，a[i-1] 的1，在a[i] 也是要有的，如果没有就是必须的，为了保证and操作后依旧为1，所以要保证a[i] xor b[i]后该位为1.。其他情况如果a[i-1]为0，但是a[i],为1就不需要管，这样贪心，可以保证我们得到的b[i]是最小的，因为我们只增加了必要的数。
总结而来我们就是需要找到 a[i] 与 (a[i-1] ^ b[i-1]) 中，a[i]没有，a[i-1]有的1.转化为十进制就可以了。
在实现上我们可以用
a[i-1]|a[i],得到所有有1的位置，再用a[i-1]| a[i] - a[i],就得到了，a[i-1]中有，打算a[i]没有的二进制了。
小结
学会了如何在得到两数二进制上，一个为1，另一位位0的操作
a|b, a|b -a//得到，b中有的1而a中没有的，a|b - b同理
代码
简单版
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N];
int b[N];
int t,n;
int main()
{
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(int i = 1;i<=n;i++) cin>>a[i];
b[1] = 0;
for(int i = 2;i<=n;i++)
{
int tmp = a[i]|a[i-1];
b[i] = tmp - a[i];
a[i] = b[i]^a[i];
}
for(int i = 1;i<=n;i++) cout<<b[i]<<" ";
cout<<"\n";
}
return 0;
}
麻烦版
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N];
int b[N];
int n;
int check(int a,int b)
{
int ans= 0;
for(int i = 31;i>=0;i--)
{
ans*=2;
if((b>>i&1)&&!(a>>i&1))
{
ans+=1;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>a[i];
b[i] = 0;
}
for(int i = 2;i<=n;i++)
{
if( (a[i]&a[i-1]) != a[i-1])
{
b[i] = check(a[i],a[i-1]);
a[i] = b[i]^a[i];
}
}
for(int i = 1;i<=n;i++) cout<<b[i]<<" ";
cout<<"\n";
}
return 0;
}
D. Ice Cream Balls
https://codeforces.com/contest/1862/problem/D
思路
问恰好有n种的冰淇淋的 最少 材料数量
仔细观察我们可以发现ice，cream的组成具有二端性，当ans个原料可以组成n及以上的ice 时，ans+x,x>=1,也是满足条件的，所以冰淇淋的组成是具有二段性的。
添加一个新的材料比加一个旧材料更好，根据题意，如果当前有n种材料的话加一个新可以得到 的新冰淇淋。如果是加上一个原有材料的话，就加上1个而已，所以每次加上一个而已，所以我们优先考虑每次加上新的。
借助二段性，我们用二分 来枚举冰淇淋的种类，当当前种类的可以达到的数量少于等于n时，我们就判断，还要加上多少种原有材料可以凑出符合条件的最小值。过程中用min 维护最小值
代码
二分版
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll l = 1;
ll r = 2e9;
ll ans = 1e18;
while(l<r)
{
ll mid = (l+r)>>1;
if( (mid)*(mid-1)/2>n )
{
r = mid;
}
else
{
ll sen = n - (mid)*(mid-1)/2;
if(sen<=mid)//当原有材料种类大于等于当前数量时
{
ans =min(ans,sen+mid);
}
l = mid+1;
}
}
cout<<ans<<"\n";
}
return 0;
}
结论版
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
void solve()
{
ll n;
cin>>n;
ll k = sqrt(2ll*n);
ll op =0;
while((k*(k-1))<=2*n)
{
op=k;
k++;
}
cout<<op+(n - (op)*(op-1)/2)<<"\n";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
E. Kolya and Movie Theatre
https://codeforces.com/contest/1862/problem/E
思路
通过题目发现一个性质，就是当最后一次是在n处时，那么最后减去的总数就是 ，因为每次减去距上一次的时间乘以d，将所有游玩天数间隔连起来就是1到n。
因此我们这里得知减去的数量，接下来就是看可以得到的最大值了。及
为了使值取最大，我们尽量使每个值取最大，就是当n为终点时，取1到n的数量最大的那个几个数之和。
- 当n小于m时，判断x是否正数，
- 当n大于等于m时，每次判断当前x是否大于最小值，是的话就是用x代替最小值。
为了维护最小值这个性质我们这里就使用小根堆。
ans维护的就是
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n,m,d;
cin>>n>>m>>d;
priority_queue<ll,vector<ll>,greater<ll>> q;
ll all=0;
ll sum=0;
ll ans=0;
ll qs=0;
for(int i = 1;i<=n;i++)
{
int x;
cin>>x;
qs+=d;
if(sum>=m)
{
if(x>q.top())
{
all-=q.top();
all+=x;
q.pop();
q.push(x);
}
}
else
{
if(x>0)
{
all+=x;;
q.push(x);
sum++;
}
}
cout<<all<<"\n";
ans = max(ans,all-qs);
}
cout<<ans<<"\n";
}
return 0;
}
Pokémon Army (easy version)
https://codeforces.com/problemset/problem/1420/C1
思路
相同题目https://www.acwing.com/solution/content/38975/
动态规划，状态机
状态设置
代码
DP
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
typedef long long ll;
ll dp[N][2];
int n,q;
int a[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
cin>>n>>q;
for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++)
{
dp[i][0] = max(dp[i-1][0],dp[i-1][1]-a[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+a[i]);
//cout<<dp[i][0]<<" "<<dp[i][1]<<"\n";
}
cout<<max(dp[n][0],dp[n][1])<<"\n";
}
return 0;
}
贪心
简单证明，在选择是 "+"的时候， 如果当前数会递增那么我们就在此时不选，如果当前数在下一次递减就选
在是"-" 的时候，会递减就不选，会递增就选
这样就保证了+的时候获得的收益最大，-的时候收益最小，那么获得总利益就最大
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
int a[N];
void solve()
{
int n,q;
cin>>n>>q;
for(int i = 1;i<=n;i++) cin>>a[i];
a[n+1] = 0;
int f =1;
long long ans=0;
for(int i = 1;i<=n;i++)
{
if(f&&a[i-1]<=a[i]&&a[i]>a[i+1])
{
ans+=a[i];
f=0;
}
else if(f==0&&a[i-1]>=a[i]&&a[i]<a[i+1])
{
ans-=a[i];
f=1;
}
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
Di-visible Confusion
https://codeforces.com/contest/1603/problem/A
思路
当前值
首先考虑处理顺序，我们发现当一个数除掉后，所有后面的数都会往前靠，所以假设当前数的下标为 那么他可以达到
的位置上，只要前面的数可以被除去。因此我们就可以从头开始查找，每个数是否可以被除去。
除数大小是 ,只要这些数中有
不可以整除的就去掉
同时 > 1e9,大于
的取值范围，所以对于下标大于22的值，一定是可以被去除的，因为a的最大值为1e9,如果要都可以整除的话，a的范围太小了，所以一定了至少找到一个数无法整除。所以剩下数直接暴力。
反证法
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int t,n,a[N];
int main(){
cin>>t;
while(t--){
cin>>n;
int flag=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int flag1=0;
for(int j=2;j<=i+1;j++){
if(a[i]%j!=0) {
flag1=1;
break;
}
}
if(!flag1){
cout<<"NO"<<endl;
flag=1;
break;
}
}
if(!flag) cout<<"YES"<<endl;
}
return 0;
}
额外
这里顺便加上一个求区间lcm的代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
const ll p = 1e9 + 7;
bitset<N> vis;
int cnt[N];//表示lcm的指数
//快速幂
ll qmi(ll a, ll b)
{
ll res = 1;
while(b)
{
if(b & 1)res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
//筛法，筛出质数
void init(int n)
{
vis[0] = vis[1] = true;
for(int i = 2;i <= n; ++ i)
if(!vis[i])for(int j = i * i;j <= n; j += i)vis[j] = true;
}
//分解质因数
void f(int n)
{
for(int i = 2;i <= n / i; ++ i)
{
if(n % i)continue;
int tmp = 0;
while(n % i == 0)n /= i, tmp ++;
cnt[i] = max(cnt[i], tmp);
}
if(n > 1)
{
cnt[n] = max(cnt[n], 1);
}
}
void solve()
{
int l, r;cin >> l >> r;
for(int i = l;i <= r; ++ i)f(i);
ll ans = 1;
for(int i = 2;i <= r; ++ i)
{
if(!vis[i])ans = ans * qmi(i, cnt[i]) % p;
}
cout << ans << '\n';
}
signed main()
{
init(4e4);
int _ = 1;
while(_ --)solve();
return 0;
}
教主的魔法
https://www.luogu.com.cn/problem/P2801
思路
问题中出现 区间修改 与 区间查询 第一想到线段树，但是 这里的k是动态的，对于每次提问k，我们都必须重新处理一次的话不太实际。
每次都重新针对k建树肯定会爆空间。
所以这里采用了时间复杂度高些，但是更加方便的 分块
对于区间加，我们用分块进行分类
- 对两端不成整块的为
直接暴力加上，更新区间，之后对其相关区间进行sort
- 对于中间成块的，采用线段树的lazy标记使用
这里需要特判如果两者在同一区间也是直接暴力加上
对于区间查询，我们使用同样用分块来分类
- 对两端不成整块的为，同上，然后遍历该范围，对于大于等于k的总结加上，记得加上懒标
- 对于成块的，总结遍历中间的每一块，因为前面我们每次都由sort，所以借用二分来查找该区间内大于等于k的位置，获得区间内大于k的数量。
如果两者在同一区间，也是直接暴力统计
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000100,M = 1010;
int a[N];
int d[N];
int block[M];
int add[M];
int bel[N];
int n,q;
int st[M];
int ed[M];
void blo()
{
int sq = sqrt(n);
for(int i =1;i<=sq;++i)
{
st[i] = n/sq*(i-1)+1;
ed[i] = n/sq*i;
}
ed[sq] = n;
for(int i =1;i<=sq;++i)
for(int j = st[i];j<=ed[i];j++)
{
bel[j] = i;
}
for(int i = 1;i<=sq;++i)
{
sort(d+st[i],d+ed[i]+1);
}
}
void change(int l,int r,int w)
{
if(bel[l]==bel[r])
{
for(int i =l;i<=r;i++)
{
a[i]+=w;
}
for(int i =st[bel[l]];i<=ed[bel[l]];i++) d[i] = a[i];
sort(d+st[bel[l]],d+ed[bel[l]]+1);
}
else
{
for(int i = l;i<=ed[bel[l]];i++) a[i]+=w;
for(int i = st[bel[l]];i<=ed[bel[l]];i++) d[i] = a[i];
sort(d+st[bel[l]],d+ed[bel[l]]+1);
for(int i = st[bel[r]];i<=r;i++) a[i]+=w;
for(int i = st[bel[r]];i<=ed[bel[r]];i++) d[i] = a[i];
sort(d+st[bel[r]],d+ed[bel[r]]+1);
for(int i = bel[l]+1;i<bel[r];i++)
{
add[i]+=w;
}
}
}
int query(int l,int r,int w)
{
int ans =0;
if(bel[l]==bel[r])
{
for(int i = l;i<=r;i++)
{
if(a[i]+add[bel[i]] >=w) ans++;
}
}
else
{
for(int i = l;i<=ed[bel[l]];i++)
{
if((a[i]+add[bel[i]] >=w) )ans++;
}
for(int i = st[bel[r]];i<=r;i++)
{
if(a[i]+add[bel[i]] >=w) ans++;
}
for(int i = bel[l]+1;i<bel[r];i++)
{
ans+=(d+ed[i]+1 - lower_bound(d+st[i],d+ed[i]+1,w-add[i]));
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>q;
for(int i = 1;i<=n;i++)
{
cin>>a[i];
d[i] = a[i];
}
blo();
while(q--)
{
string s;
cin>>s;
if(s=="M")
{
int l,r,w;
cin>>l>>r>>w;
change(l,r,w);
}
else
{
int l,r,k;
cin>>l>>r>>k;
cout<<query(l,r,k)<<"\n";
}
}
}
D - Count Interva
思路
偏水题。
问有多少连续子段和等于k；
先做一个前缀和和一个哈希表，然后从头遍历，查看 有多少直接查找。
这里需要提前加上 ma为哈希表，表示可以从头到尾
这里map查找的时间复杂度为
hash_map
时间复杂度
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int N = 200010;
ll a[N];
int n;
ll k;
map<ll,ll> ma;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>k;
for(int i = 1;i<=n;i++)
{
ll x;
cin>>x;
a[i] = a[i-1]+x;
}
ma[0] = 1;
ll sum=0;
for(int i = 1;i<=n;i++)
{
sum +=ma[(a[i]-k)];
ma[(a[i])]++;
}
cout<<sum<<"\n";
return 0;
}
2xN Grid
https://atcoder.jp/contests/abc294/tasks/abc294_e
思路
数列的长度开得很大，所以不可能 一个一个枚举，而是使用题目给出的区间进行枚举。
每次枚举两个区间，看是否有相同数字，没有就将其中小的一个向后走，不断枚举。
有相同的话，就加上其相交区间大小。
时间复杂度
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll ;
const int N = 100010;
ll a1[N];
ll b1[N];
ll a2[N];
ll b2[N];
int n,m;
ll l;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>l>>n>>m;
for(int i = 1;i<=n;i++) cin>>a1[i]>>b1[i];
for(int i = 1;i<=m;i++) cin>>a2[i]>>b2[i];
ll ans =0;
ll l1=b1[1];
ll l2=b2[1];
int a=1;
int b=1;
while(a<=n&&b<=m)
{
if(a1[a]==a2[b])
{
ll x= l1 - b1[a];
ll y= l2 - b2[b];
ans+=(min(l1,l2) - max(x,y));//加上的数是不会有小于0的情况的
/*
假设出现小于0的情况说明出现了，一段的左端，设为r严格大于一端的右段设为l，，说明r的前一区间r-1的右端是大于
当前l的右端的，但是这一情况如果出现的话，会被下面的区间增加判断，l会变成l+1,而不是l，前后矛盾，所以不会有出现小于0的情况
*/
}
if(l1>=l2)
{
l2+=b2[++b];
}
else
{
l1+=b1[++a];
}
}
cout<<ans<<"\n";
return 0;
}
京公网安备 11010502036488号