第二周
MooFest
https://vjudge.net/problem/POJ-1990
思路
树状数组，排序
先按分贝排序，然后用两个树状数组来存储 在节点个数和在节点的距离和，查询大于当前坐标的数量与距离和 小于当前坐标的数量与距离，
当前坐标和 减去 大于数量乘以坐标 乘以分贝，加上 小于数量乘以坐标 减去 坐标和 乘以分贝。累加就可以了。
写的时候数组越界了，下标从1开始结果写sort的时候没加上1
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 20010;
PII xy[N];
ll tr1[N]={0};
ll tr2[N]={0};
ll n;
ll lowbit(int x)
{
return x&-x;
}
void add(ll tr[],ll x,ll c)
{
for(ll i = x;i<N;i+=lowbit(i)) tr[i]+=c;
}
ll sum(ll tr[],ll x)
{
int res =0;
for(ll i =x;i;i-=lowbit(i))
{
res+=tr[i];
}
return res;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n;
//cout<<tr[N<<endl;
// cout<<sum(tr2,N)<<endl;
for(int i = 1;i<=n;i++)
{
int v,x;
cin>>v>>x;
xy[i] ={v,x};
}
ll ans =0;
sort(xy+1,xy+n+1);
//cout<<sum(tr2,N)<<endl;
for(int i = 1;i<=n;i++)
{
int x = xy[i].first;
int y = xy[i].second;
//cout<<x<<" "<<y<<"\n";
ll x1 = sum(tr1,N-1) - sum(tr1,y);//比y大的所有坐标的和
ll x2 = sum(tr1,y); //比y小的所有坐标的和
ll y1 = sum(tr2,N-1) - sum(tr2,y);//比y大的所有坐标的数量
ll y2 = sum(tr2,y);//比y小的所有坐标的数量
//cout<<" "<<y1<<" "<<y2<<" "<<x1<<" "<<x2<<"\n";
ans+= 1ll*x*(x1 - y1*y );
ans+= 1ll*x*(y2*y - x2 );
add(tr1,y,y);
add(tr2,y,1);
}
cout<<ans<<"\n";
return 0;
}
Matrix
https://vjudge.net/problem/POJ-2155
思路
二维差分，二维树状数组
差分的方式记录每一次的矩阵修改，发现可以整除2就是0，不是就是1，所以我们就只要记录修改次数就可以了。
因为是动态的查询和修改所以我们是无法用一般的二维差分做的，所以用上了树状数组来继续优化，将修改变成了
级别，因为是差分所以将求和查询变成了单点查询。
一开始没想好矩阵修改的方式，以为可以变成一维的树状数组来继续操作，不过这样无法确定一个唯一方式来修改矩阵所以是错误的
也认识到树状数组其实本质就是用二进制lowbit来迭代数组，所以可以用在矩阵差分上
代码
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 1003;
char s[5];
int a[maxn][maxn], n;
int lowbit(int x) {
return (x & (-x));
}
void update(int x, int y) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= n; j += lowbit(j)) {
a[i][j]++;
}
}
}
int sum(int x, int y) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j))
res += a[i][j];
}
return res;
}
int main() {
int ca, t;
int x, y, u, v;
scanf("%d", &ca);
while (ca--) {
memset(a, 0, sizeof(a));
scanf("%d%d", &n, &t);
while (t--) {
scanf("%s%d%d", s, &x, &y);
if (s[0] == 'C') {
scanf("%d%d", &u, &v);
x++, y++;
u++, v++;
update(u, v);
update(x - 1, y - 1);
update(x - 1, v);
update(u, y - 1);
}
else {
printf("%d\n", sum(x, y) % 2);
}
}
printf("\n");
}
return 0;
}
D. Absolute Sorting
https://codeforces.com/contest/1772/problem/D
思路
问是否有一个数，让序列中的所有数 与他的差值取绝对值，使得序列变为非降序的序列
假设这个数为x，那么要求每一个
这里需要分情况讨论
- 当 那么 x等于什么数都无所谓，都可以
- 当
- ￥ 需保证 满足
- 需保证
- 需保证 即 x <= (a1+a2)/2 //右边界
- 当 a1 >a2
- 当 要满足 x - a1 <= x -a2 ， x>=a1 符合条件
- 当 满足 a1 - x <= a2 -x 不和条件
- 满足 a1 - x <= x - a2 即 x>=(a1+a2)/2; //左边界 ，
学到如何分类讨论带绝对值的情况
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N];
int t;
int 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];
int l = 0;
int r = 1000000000;//题目保证数据范围有解
for(int i = 1;i<n;i++)
{
if(a[i]>a[i+1])
{
l = max(l,(a[i]+a[i+1]+1)/2);//这里有一个边界问题，以为x>=(a1+a2)/2,因为是下取整可能导致最小值变小，为了保证严格需要加1做上取整
}
else if(a[i]<a[i+1])
{
r = min(r,(a[i]+a[i+1])/2);
}
}
if(l>r) cout<<"-1\n";
else cout<<l<<"\n";
}
return 0;
}
Particles
https://vjudge.net/problem/CodeForces-1844C
思路
抽走中间的数可以让其，左右两个数合并成一个 ，问任意操作后可以得到的最大值是多少？
（下标从1开始）将序列看成 那么抽掉 的话，就是 相加，i和i+2的奇偶性相同，所以我们可以发现，无论怎么抽，都是奇数位的数加上奇数位的数，偶数位的数加上偶数位的数。而且任意奇数下标为可任意相加。偶数下标也相同。
证明 如果想让 a i + ai +4 的话，就是先抽去 a i+2,再抽取 （ai+1 + ai+3);
所以 所以可以任意奇数下标的数都可以加上，偶数同理
特判 加入全是负数的话，明显最大值就是序列中的最大数
时间复杂度
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 200010;
int a[N];
int t;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>t;
while(t--)
{
int n;
cin>>n;
int ma = -0x3f3f3f3f;
//cout<<ma<<endl;
int f = 0;
for(int i = 1;i<=n;i++)
{
cin>>a[i];
if(a[i]>0) f =1;
ma = max(a[i],ma);
}
ll len1=0;
ll l1=0;
ll len2=0;
ll l2=0;
for(int i = 1;i<=n;i+=2)
{
//cout<<l1<<endl;
l1+= max(0ll,1ll*a[i]);
//len1 = max(l1,len1);
}
// cout<<endl;
for(int i = 2;i<=n;i+=2)
{
//cout<<l2<<endl;
l2+= max(0ll,1ll*a[i]);
}
// cout<<len1<<" "<<len2<<"\n";
if(f)cout<<max(l2,l1)<<"\n";
else cout<<ma<<"\n";
}
}
Matching
https://atcoder.jp/contests/dp/tasks/dp_o
思路
首先从题目的数据范围和输入的矩阵上已经在暗示用 状态压缩DP （n最大不过22）
状态表示
我们用
状态的转移
时间复杂度
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 22,mod = 1e9+7;
int dp[1<<N];
int n;
int match[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
{ cin>>match[i][j]; }
dp[0]=1;//0个男人匹配0个女人的方案只有1个
for(int i = 1;i< ( 1<<n); i++)
{
int i1 = i;
int t = 0;
// cout<<i1<<endl;
while(i1)//获得i中1的个数
{
t++;
i1 = i1 - (i1&-i1);
}
//cout<<t<<"\n";
for(int j = 1;j<=n;j++)
{
if(match[t][j]&&( i>>(j-1))&1 )
{
dp[i]+= (dp[i - ( 1<<(j-1) )]);
dp[i]%=mod;
}
}
}
cout<<dp[ (1<<n) - 1];
return 0;
}
E. Living Sequence
https://codeforces.com/problemset/problem/1811/E
思路
假设取掉4，问10进制中，第n大的数是多少。
先从更大的方面开始分析，十进位制中去掉一个数，要求这个数不出现，问第几大的数是多少？
在十进制中某个数不出现，也就是少了一位数字来表示，也就是9进制了。
那么问题就是在问，在九进制中，第x个数是多少。这个我们可以直接从10进制中转化，因为进制不影响表示的数值大小，转化为9进制后，反转数组然后判断每一位是的数字大小，小于4就不变，大于4就加一。这里只是在表示上变化了而已，将消失的9改为消失的4.
进位制的表示是数值大小的表示,对大小本身不影响
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
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 ans;
vector<int> a;
//cout<<ans<<"\n";
cin>>ans;
while(ans)//进制转换
{
a.push_back(ans%9);
ans/=9;
}
reverse(a.begin(),a.end());//反转数组
for(int i = 0;i<(int)a.size();i++)
{
int k = a[i];
if(k<4) cout<<k;
else cout<<k+1;
}
cout<<endl;
}
return 0;
}
线段树
https://www.luogu.com.cn/problem/P3372
思路
区间修改，区间求和纯板子，
代码
//记录容易写错的地方
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
typedef long long ll;
struct node
{
int l,r;
ll sum;
ll add;
}tr[N*4];
int n,q;
int w[N];
void pushup(int u)//因为此题查询区间和，所以这里维护区间和
{
tr[u].sum = (tr[u*2].sum + tr[u*2+1].sum);
}
void pushdown(int u)//向下，传递lazy标记
{
if(tr[u].add)
{
tr[u*2].add+=tr[u].add;
tr[u*2].sum+=(ll)(tr[u*2].r - tr[u*2].l+1)*tr[u].add;
tr[u*2+1].add+=tr[u].add;
tr[u*2+1].sum+=(ll)(tr[u*2+1].r - tr[u*2+1].l+1)*tr[u].add;
tr[u].add=0;
}
}
void build(int u,int l,int r)//l和r为此节点u所代表的区间范围
{
if(l==r) tr[u] ={l,r,w[l],0};//区间中只有一个数代表为叶子节点，完成赋值
else
{
tr[u] = {l,r};//直接对建立好的节点赋值
int mid = l + r>>1;
build(u*2, l,mid);//对其左子树赋值
build(u*2+1,mid+1,r);//对其右子树赋值
pushup(u);//向父节点更新信息
}
}
void modify(int u,int l,int r,int d)//表示以u为当前查询到的节点，对区间【l,r】中的数加上d
{
if(tr[u].l>=l&&tr[u].r<=r)//如果当前u表示的区间，被要求区间完全包围，就直接对u直接修改
{
tr[u].sum+=(ll)(tr[u].r - tr[u].l + 1)*d;
tr[u].add+=d;
}
else
{
pushdown(u);//更新lazy 标记，更新子树的信息
int mid = tr[u].l + tr[u].r >>1; //获得u的左右子树的分节点
if(l<=mid) modify(u*2,l,r,d);//如果修改区间与其左子树有重叠，递归其左子树
if(r>mid) modify(u*2+1,l,r,d);//同上
pushup(u);//向父节点更新信息
}
}
ll query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >>1;
ll sum =0;
if(l<=mid) sum+=query(u*2,l,r);
if(r>mid) sum+=query(u*2+1,l,r);
return sum;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>q;
for(int i = 1;i<=n;i++) cin>>w[i];
build(1,1,n);//1表示以1为编号为根节点，建立的区间为l到r
//for(int i = 1;i<=n;i++) cout<<query(1,i,i)<<" ";
//cout<<endl;
while(q--)
{
string op;
int l,r;
cin>>op;
if(op=="1")
{
int d;
cin>>l>>r>>d;
modify(1,l,r,d);
}
else
{
cin>>l>>r;
cout<<query(1,l,r)<<"\n";
}
// for(int i = 1;i<=n;i++) cout<<query(1,i,i)<<" ";
// cout<<endl;
}
return 0;
}
AtCoder Beginner Contest 312
B
思路
枚举,判断,写起来麻烦点
代码
这里参考jly的写法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n,m;
cin>>n>>m;
vector<string> S(n);
for (int i = 0; i < N; i++) {
std::cin >> S[i];
}
for (int i = 0; i + 8 < n; i++) {
for (int j = 0; j + 8 < m; j++) {
int f = 1;
for (int x = 0; x < 4; x++) {
for (int y = 0; y < 4; y++) {
if (S[i + x][j + y] != (x == 3 || y == 3 ? '.' : '#')) {
f = 0;
}
if (S[i + 8 - x][j + 8 - y] != (x == 3 || y == 3 ? '.' : '#')) {
f = 0;
}
}
}
if (f) {
cout << i + 1 << " " << j + 1 << "\n";
}
}
}
return 0;
}
C
思路
排序加二分
题目问的是求一个最小的X.满足愿意以X及X以上买的人数,大于等于愿意以X及X以下的人数
我们设a为存储卖家的数组
b为储存买家的数组,将a.b 从小到大排序
首先我们要考虑下如何判断一个数x是否符合条件.
- 看在 a数组中有多少个数 小于等于x,这里我们可以用 upper_bound 得到数组中严格大于x的下标即我们所要求的数量
- 看在 b数组中有多少个数 大于等于x,这里我们可以用 lower_bound 得到数组中大于等于x的下标,在用数组大小减去下标,就得到有多少数符合条件
那么如何判断最小呢
对于这类区间中取最小值或者最大值的问题,我们一般采用二分,对X采用二分,每次循环中进行两次二分,
这里取值范围是1到1e9,所以我们将范围设置为1到1e10,(设为1e9的话,如果买家都是1e9的话,那么数值应该是1e9+1)
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200010;
vector<long long> a;
vector<long long> b;
int n,m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
int x;
cin>>x;
a.push_back(x);
}
for(int i = 1;i<=m;i++)
{
int x;
cin>>x;
b.push_back(x);
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
long long l = 1;
long long r =1e10;
while(l<r)
{
// cout<<l<<" "<<r<<" ";
long long mid = l + r >>1;
// cout<<mid<<endl;
int x = upper_bound(a.begin(),a.end(),mid) - a.begin();
int y = lower_bound(b.begin(),b.end(),mid) - b.begin();
//cout<<x<<" "<<y<<endl;
//y = m - y;
if( y <= x) r = mid;
else l = mid+1;
}
cout<<l<<"\n";
}
D
思路
DP,括号匹配,需要了解以下两个性质
- 前i个字符中,左括号的数量必须大于等于右括号
- 最后左括号的数量要等于右括号的数量
因此我们这里思考下状态的表示
/*dp[i][j] 为前i字符中有j个左括号的数量,当时我们可以发现这样的表示是有局限的,比如 ))((,就符合条件表示但不是我们所要求的
所以我们要加上前面写的第一个性质 左括号必须大于等于右括号.
那么我们的就不会有错误情况加入了. */
接下来考虑如何转移
/*当括号为"("时,我们可以直接转移,dp[i][j] = dp[i-1][j-1]
当括号为")"时,我们可以需要判断 (加上后左括号需要继续大于右括号) if(j >= i - j) dp[i][j] = dp[i-1][j]
为"?" 有两种情况,为"(" 按"("的情况处理
为")" 按")"的情况处理
最后需要判断字符数量,如果为奇数就为0,因为不和性质,偶数就输出dp[n][n/2];
*/
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 998244353, N = 3010;
int dp[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string str;
cin>>str;
int n = str.size();
// cout<<n<<endl;
str =' '+str;
//cout<<str<<endl;
dp[0][0] = 1;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=i;j++)
{
if( str[i]==')' )
{
if(j>=i-j) dp[i][j]=dp[i-1][j];
dp[i][j]%=mod;
}
else if(str[i]=='(')
{
dp[i][j] = dp[i-1][j-1];
dp[i][j]%=mod;
}
else
{
dp[i][j] = dp[i-1][j-1];
if(j>=i-j)
{
dp[i][j] = (dp[i][j] + dp[i-1][j]);
dp[i][j]%=mod;
}
}
}
}
cout<<(n%2 ? 0 : dp[n][n/2])<<"\n";
return 0;
}
F
思路
排序,贪心
求 0 到 n的A罐头感前缀和
求0 到 n 的B罐头后缀和
然后枚举用多少个A罐头,与前后缀之和作比较,求最大值
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> a;
vector<ll> b;
vector<ll> c;
int n,m;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
int t,x;
cin>>t>>x;
if(t==0) a.push_back(x);
else if(t==1) b.push_back(x);
else c.push_back(x);
}
vector<ll> op(n+1);
vector<ll> xq(n+1);
sort(a.begin(),a.end(),greater<>());
sort(b.begin(),b.end());
sort(c.begin(),c.end());
求前缀值
for(int i = 0;i<n;i++)
{
if(i<a.size()) op[i+1] = op[i]+a[i];
else
{
op[i+1] = op[i];
}
}
//求后缀值
int r = 0;
for(int i = 0;i<n;i++)
{
if(b.empty()) xq[i+1] = xq[i];
else if(r==0)
{
if(!c.empty()){
r+=c.back();
c.pop_back();
}
xq[i+1] = xq[i];
}
else
{
r--;
xq[i+1] = xq[i]+b.back();
b.pop_back();
}
}
ll ans = 0;
for(int i = 0;i<=m;i++) ans = max(ans,op[i]+xq[m-i]);
cout<<ans;
return 0;
}
E
思路
set,枚举
两个长方体若会贴着，则存在两个小正方体分别属于这两个长方体，且两个小正方体在某一方向连续，因此考虑枚举小正方体
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N = 120;
int sw[N][N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin>>n;
for(int i = 1;i<=n;i++)
{
int x1,y1,z1;
int x2,y2,z2;
cin>>x1>>y1>>z1>>x2>>y2>>z2;
for(int x = x1;x<x2;x++)
{
for(int y = y1;y<y2;y++)
{
for(int z = z1;z<z2;z++)
{
cout<<"s"<<endl;
sw[x][y][z] = i;
}
}
}
}
vector<set<int>> s(n+10);
for(int i = 0;i<100;i++)
{
for(int j = 0;j<100;j++)
{
for(int k = 0;k<100;k++)
{
int o = sw[i][j][k];
int x = sw[i+1][j][k];
int y = sw[i][j+1][k];
int z = sw[i][j][k+1];
//cout<<x<<" "<<y<<" "<<z<<endl;
if(!o)
{
continue;
}
if(x&&o!=x)
{
s[o].insert(x);
s[x].insert(o);
}
if(y&&o!=y)
{
s[o].insert(y);
s[y].insert(o);
}
if(z&&o!=z)
{
s[o].insert(z);
s[z].insert(o);
}
}
}
}
for(int i = 1;i<=n;i++)
{
cout<<s[i].size()<<"\n";
}
return 0;
}
京公网安备 11010502036488号