学校周赛（2）
A.Minimize!
题目
思路
本题只需要遍历c的取值，实时更新答案即可
代码
#include<iostream>
#include<algorithm>
using namespace std;void todo(){int a,b;cin>>a>>b;int ans=INT_MAX;for(int c=a;c<=b;c++){ans=min(ans,(c-a)+(b-c));}cout<<ans<<endl;
}int main(){int t;cin>>t;while(t--){todo();}return 0;
}
B.osu!mania
题目
思路
本题只需要将图从下到上进行遍历并记录#的位置即可
代码
#include<iostream>
#include<vector>
using namespace std;void todo() {vector<int> ans;int n; cin >> n;int num;vector<string> cnt(n);for (int i = 0; i < n; i++) {cin >> cnt[i];}num = cnt[0].size();for (int i = n-1; i >=0; i--) {for (int j = 0; j < num; j++) {if (cnt[i][j] == '#') {ans.push_back(j+1);}}}for (int x : ans) {cout<<x<<" ";}cout << endl;
}int main() {int t; cin >> t;while (t--) {todo();}return 0;
}
C.The Legend of Freya the Frog
题目
思路
首先我们将路分为沿x和沿y方向进行考虑，分别计算两者至少需要几步，由于每次都是先向x轴方向前进，所以如果是x大的话则y比x要少走一步，如果y大或者y==x时，说明y和x走了相同的步数。
代码
#include<iostream>
#include<vector>
using namespace std;void todo() {int ans = 0;int x, y, k;cin >> x >> y >> k;//至少走几步x = ((x % k) ? 1 : 0)+ x / k;y = ((y % k) ? 1 : 0)+y / k;//cout << x << " " << y<<endl;ans = (x > y) ? (x*2-1):(y*2) ;cout << ans << endl;
}int main() {int t; cin >> t;while (t--) {todo();}return 0;
}
D.Satyam and Counting
题目
思路
本题我采用的方法时哈希+维护的方式，首先记录y=0，y=1，以及每一个x位置的点数，我们进行一个枚举和判断，我们枚举与y轴平行的高进行分析。
第一次枚举：当高为直角边（此处对应x为两个点）时，是一个组合，取y=1的作为另一个直角边，可以组成y[1]-1个三角形，同理y=0时，对应的时y[0]-1，总和起来时y[0]+y[1]-2
第二次枚举：当高不为直角边时（设顶点为（x，y）），查看与其y不相同的线上是否存在两个点组成直角三角形，由于本题的特殊性高一定为1，所以想要续成直角边，对应其余两点的x坐标一定是x-1,y-1。
代码
#include<iostream>
#include<vector>
using namespace std;void todo() {long long ans = 0;int n; cin >> n;vector<vector<int>> cnt(n + 1, vector<int>(2));vector<int> cnt_x(n + 1);vector<int> cnt_y(n + 1);for (int i = 0; i < n; i++) {int x, y;cin >> x >> y;cnt[x][y]++;cnt_x[x]++;cnt_y[y]++;}//维护一个直角边,平行于y轴的边for (int i = 0; i < n + 1; i++) {if (cnt_x[i] == 2) ans += cnt_y[0] + cnt_y[1] - 2;}for (int i = 1; i < n; i++) {if (cnt[i][0] && cnt[i - 1][1] && cnt[i + 1][1]) ans++;if (cnt[i][1] && cnt[i - 1][0] && cnt[i + 1][0]) ans++;}cout << ans << endl;
}int main() {int t; cin >> t;while (t--) {todo();}return 0;
}
E.Klee’s SUPER DUPER LARGE Array!!!
题目
思路
本题考查的是数学+二分，在数学方面考察了一个等差数列求和，一个二次函数最值问题。
我们通过二分去寻找我们对应的i，我们按照题目意思将其分为左右两侧分别求和sum1 sum2，我们对应的答案则为|sum1-sum2|，通过化简得到[(2k+i)(i+1)-(n-i-1)(2k+n+i)]/2，不难看出这是一个二次函数，我们取绝对值之后，最小的结果对应着与0最接近的点，我们统计大于0当中最近的点，和小于0中最接近的点，最后返回其中对应的最小答案
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;//等差数列
long long sum(long long a, long long b) {return ((b - a + 1) * (a + b)) >> 1;
}void todo() {int n, k; cin >> n >> k;int l = 0, r = n-1 ; while (l+1 < r) {int i = (l + r) / 2;long long sum1 = sum(k,k+i);long long sum2 = sum(k+i+1,k+n-1);//ans=abs(sum1-sum2)=| [(2k+i)(i+1)-(n-i-1)(2k+n+i)]/2 | ==> 二次函数//要绝对值最小则就是使答案向0逼近//找到左右侧距离0最近的两个点if (sum2-sum1>0) {l = i; }else { r = i; }}//返回两点之间的最小值cout << min(abs(sum(k, k + l) - sum(k + l + 1, k + n - 1)), abs(sum(k, k + r) - sum(k + r + 1, k + n - 1))) << endl;
}int main() {int t; cin >> t;while (t--) {todo();}return 0;
}
F. Firefly’s Queries (补题中)
题目
