前言
好久没写了 这几天一直说写 本来昨晚写 但是昨晚9点回来洗衣服跑步洗澡吃饭
弄完了累得半死上了会网 就12点多了 然后就关机了 后面就玩了会手机什么的睡觉了
第一个题目
这个题以前做过类似的
但是忘了咋做了 然后一直脑抽 就是想二分写 结果给自己写炸毛了
这道题 有两个写法
第一种是双指针写法 说实话 这个双指针挺有意思的
Here
点击查看代码
for(int i=0,j=n-1;i<j;i++){//右边界遍历
while(i<j&&a_a[i]+a_a[j]>r)j--;//寻找加和小于r的右边界
if(j-i<0)break;//跳出循环
ans+=j-i;
}
for(int i=0,j=n-1;i<j;i++){//左边界遍历
while(i<j&&a_a[i]+a_a[j]>=l)j--;
if(j-i<0)break;
ans-=j-i;
}
第二种是二分查找的写法
我这道题对于ai分类分成大于L和小于L去写 然后二分 对于大于L：对于缺少的那一块用二分去查找 小于L：
二分直接查找r-a[i] 和l-a[i]的 不知道为什么写炸毛了
因为我是倒序写的 处理区间出错
Here
点击查看代码
for (int i = 1; i <=n ; i++) {
int x1=lower_bound(a+1+i,a+1+n,l-a[i])-a;
int x2=lower_bound(a+1+i,a+1+n,r-a[i])-a;
if(x1>x2)continue;
if(x2==n+1||a[x2]>r-a[i])x2--;
ans+=x2-x1+1;
cout<<ans<<endl;
}
第二个
这题已经写过题解了 在洛谷专栏里面
反正学到技巧就是 打表线性筛再做时间更快
第三个
我是求了一个平均值 然后对于这个平均值进行+1进行递增 弄完了之后多了开始减就行了 这样是保证有解的 感觉就像是以前做过一样
第四个
都是直接切的题 就不多说了 就是一个暴力枚举
第五个
这道题是个板子 但我做的过程中出现了意外
讨论区
留着以后解决
第六个
这题一开始还以为是最短路
结果发现是个找规律吧题
说下我为什么没做出来 就是分类不细致 然后导致没找到正确的写法 最终没写出来 其实就是两种情况 偶数与奇数 然后对于同一个路线 就是i+k=j+k呗 这边就要注意到 偶数 奇数问题 我tm就是因为这个没好好归纳出来结果 很明显的对于 二者不是一条路线的 你要计算他左移的次数 其实就是偶数免费走一次然后没了 对于同一个路线的就好说多了
if (y - x == yy - xx) {
if ((x + y) % 2 == 0) {
ans += xx - x;
}
}
对于这个我没有想到 同一个路线 但是我是偶数时就这个没想到了
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int range = 2e5 + 10;
int n;
pair<int, int>p[range];
int a[range];
bool cmp(pair<int, int>x, pair<int, int>y) {
return x.first < y.first;
}
void solve() {
cin >> n;
for (int i = 2; i <= n+1; i++)
cin >> p[i].first;
for (int i = 2; i <= n+1; i++)
cin >> p[i].second;
p[1]={1,1};
sort(p + 1, p + 2 + n);
int ans = 0;
for (int i = 2; i <= n+1; i++) {
int x = p[i-1].first;
int y = p[i-1].second;
int xx = p[i].first;
int yy = p[i].second;
if(xx==1&&yy==1)continue;
if (y - x == yy - xx) {
if ((x + y) % 2 == 0) {
ans += xx - x;
}
} else {
if ((x + y) % 2 == 0) {
int del = xx - (x + 1);
y += del;
ans += (y - yy + 2 - 1) / 2;
} else {
int del = xx - x;
y += del;
ans += (y - yy + 2 - 1) / 2;
}
}
// cout<<x<<" "<<y<<" "<<ans<<" "<<i<<endl;
}
cout << ans << endl;
return ;
}
signed main() {
int t ;
cin >> t;
while (t--)
solve();
}
第七个
这道题我一开始写了个ss的代码
代码
然后调的不想调了 遂看题解 感觉智商是负的
这题是一个模板的单调队列/栈的题目了
还是自己这方面题做的太少了 脑子没这个思路
题目很好 说实话 受益匪浅
栈和队列最大的区别就是 后进先出了
比如 1 2 读入栈里 输出 2 1 队列就不是了 2读入是放在1后面的 所以输出front是1 2
第八个
题目很好
我当时赛事猜的时候 不知道怎么写头元素的写法 于是写首尾匹配 这是错的 我的思路其实存在错误 我只是贪心的想让一层多挂几个 就是那些层数为1的尽量往前挂 然后再是2这些 但是呢 这其实不对 那些层数为1的怎么挂最终都会有几个挂后面 对于最远距离还是没有改进 还是得一层层挂层数大的 这题主要考猜
第九题
这题很有讲的必要 我tle原因在于随意使用unordermap导致的 以后不要乱用 这个只拿来插 别拿来++这些操作 不然多了时间是线性的 On的for都进行不了 还要就是map的访问 这个下面会讲的 对于他的操作都会插入新元素 除非已经拥有
ps 我一开始还ump以为hash冲突了
第10个
此题比较简单 不讲 但为什么放呢
if (vis[sum[i]])continue;
//虽然ma1 没用访问 然后结束 但是你对ma1进行访问判断 传入了ma1的值
就这个
第十一个
这道题贪心很好想
但是很容易贪的不够！
对于2个1>2的那种 我们不是一次性把2个1全拿 而是把头顶的那个1拿了就行 这步实在太秒了
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int range = 3e5 + 10;
int n;
int a[range];
int m;
int b[range];
int sum = 0;
int one[range];
int two[range];
int step1 = 0;
int step2 = 0;
void init() {
for (int i = 1; i <= step1 + 100; i++)one[i] = 0;
for (int i = 1; i <= step2 + 100; i++)two[i] = 0;
}
void solve(int t) {
cin >> n >> m;
step1 = step2 = 0;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)cin >> b[i]; //,sum+=b[i];
//想dp的 但是Onsum做不了cao
for (int i = 1; i <= n; i++) {
if (b[i] == 1) one[++step1] = a[i];
else two[++step2] = a[i];
}
sort(one + 1, one + 1 + step1, greater<int>());
sort(two + 1, two + 1 + step2, greater<int>());
int l = 1;
int r = 1;
int ans = 0;
sum = 0;
one[step1 + 1] = 0;
two[step2 + 1] = 0;
while (m > sum && (l <= step1 || r <= step2)) {
// cout<<sum<<" "<<l<<" "<<r<<endl;
if (r >step2) {
// cout<<step2<<endl;
for (int i = l; i <= step1; i++) {
sum += one[i];
ans += 1;
if (sum >= m)break;
}
break;
}
if (l >step1) {
//cout<<sum<<endl;
// cout<<r<<endl;cout<<step2<<endl;
for (int i = r; i <= step2; i++) {
sum += two[i];
//cout<<sum<<endl;
ans += 2;
if (sum >= m)break;
}
//cout<<sum<<endl;
break;
}
// cout<<sum<<" "<<l<<" "<<r<
if (sum + one[l] >= m) {
sum += one[l];
ans += 1;
// cout<<sum<<endl;
break;
}
else if (one[l] + one[l + 1] >= two[r] && l + 1 <= step1) {
// ans += 2;
// sum += (one[l] + one[l + 1]);
// l += 2;
//小小的改动 想不出来的人哪里会知道多难
ans += 1;
sum += (one[l] );
l += 1;
} else if (r <= step2) {
// cout<<sum<<endl;
ans += 2;
sum += two[r];
r += 1;
} else {
break;
}
}
// cout<<sum<<endl;
if (sum < m) {
cout << -1 << endl;
return ;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for(int i=1;i<=t;i++)
solve(i);
return 0;
}
/*
1
4 13
3 4 2 4
1 2 2 2
2 4 4 2
1 3
*/
第十二个
这是个下午刚做的题目 这是一个矩阵异或 我想了半天怎么做就是没想到去把两个矩阵异或掉 然后你会发现异或得到的矩阵就是我们操作的矩阵 而这个矩阵初始是全部是0是我们通过很多步骤让他变成我们是二者相等的矩阵
那问题就转化为 这个矩阵可以通过一定次数回到0吗
就这么一个问题也要动脑筋的
很显然 我们假设可以 很明显对于每一行来说 最终都是一样的 然后经过一次竖直操作变成0 那问题就是从第二行开始可以通过一次操作变成1与否
如果一行中存在0也有1 很明显不行
于是做完
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int range = 1e3 + 10;
int n;
int a[range][range];
int b[range][range];
int num[range][range];
int xsum[range];
int ysum[range];
void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
a[i][j] = b[i][j] = ' ';
}
}
//真是菜狗一只了 都没想到矩阵异或
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
char ch;
cin >> ch;
if (ch == '1')a[i][j] = 1;
else a[i][j] = 0;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
char ch;
cin >> ch;
if (ch == '1')b[i][j] = 1;
else b[i][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)a[i][j] ^= b[i][j];
}
for (int i = 2; i <= n; i++) {
bool flag1 = 0;
bool flag2 = 0;
for (int j = 1; j <= n; j++) {
if (a[i][j] == a[1][j])flag1 = 1;
else if (a[i][j] != a[1][j])flag2 = 1;
}
if (flag1 && flag2) {
cout << "NO" << endl;
init() ;
return ;
}
}
init();
cout << "YES" << endl;
return ;
}
signed main() {
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
//void solve() {
// cin >> n;
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= n; j++)
// cin >> a[i][j];
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= n; j++)
// cin >> b[i][j];
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= n; j++) {
// if (a[i][j] == '1' && b[i][j] == '1')
// num[i][j] = 2;
// else if (a[i][j] == '1' && b[i][j] == '0')
// num[i][j] = 1;
// else if (a[i][j] == '0' && b[i][j] == '0')
// num[i][j] = 2;
// else if (a[i][j] == '0' && b[i][j] == '1')
// num[i][j] = 1;
// }
// //判断有无这种情况 奇 全是偶数
//
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++)xsum[i] = xsum[i] + num[i][j];
// }
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++)ysum[i] = ysum[i] + num[j][i];
// }
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// cout<<num[i][j]<<" ";
// cout<<endl;
// cout<<xsum[i]<<endl;
// cout<<endl;
// }
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)
// {
// if((xsum[i]-num[i][j])%2==0&&(ysum[j]-num[i][j])%2==0&&num[i][j]%2){
// cout<<i<<" "<<j<<endl;
// cout<<xsum[i]-num[i][j]<<" "<<ysum[j]-num[i][j]<<endl;
// cout<<"NO"<<endl;
// init();
// return ;
// }
// }
// }
// cout<<"YES"<<endl;
// init();
很好的一道题