T1：
本题AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int k;
cin >> k;
map<ll,ll>cnt1,cnt2;
for (int i=0;i<k;++i){
ll r,c;
cin>>r>>c;
cnt1[r-c]++;
cnt2[r+c]++;
}
ll ans = 0;
for (auto& p:cnt1){
ll x=p.second;
ans+=x*(x-1)/2;
}
for (auto& p:cnt2){
ll x = p.second;
ans+=x*(x-1)/2;
}
cout << ans << endl;
return 0;
}
本题思路：
使用哈希表（字典）来高效统计每个对角线值的出现次数。
T2：
本题AC代码：
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100005],b[100005],ans=0;
map<long long,long long>cnt;
int main(){
cin>>n>>k;
cnt[0]=1;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=b[i-1]^a[i];
}
for(int i=1;i<=n;i++){
ans+=cnt[k^b[i]];
cnt[b[i]]++;
}
cout<<ans;
return 0;
}
本题思路：
利用前缀异或和结合哈希表进行统计，可以在 O(n) 时间内解决问题。
T3：
本题AC代码：
#include<bits/stdc++.h>
using namespace std;
long long n,sb1[100005],sb2[100005],ans=0x3f3f3f3f3f3f3f3f;
struct node{
long long a,b;
};
bool cmp(node n1,node n2){return n1.a<n2.a;}
node a[100005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].b;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
sb1[i]=sb1[i-1]+a[i].b,sb2[i]=sb2[i-1]+a[i].a*a[i].b;
}
for(int i=1;i<=n;i++){
ans=min(ans,a[i].a*sb1[i]-sb2[i]-a[i].a*(sb1[n]-sb1[i])+sb2[n]-sb2[i]);
}
cout<<ans<<"\\n";
return 0;
}
本题思路：
步骤1：排序村庄位置
将所有村庄按位置 a[i] 从小到大排序。这一步是为了方便后续计算左右两侧的权重和。
步骤2：计算总人口
计算所有村庄的总人口。
步骤3：寻找加权中位数
遍历排序后的村庄，累加人口权重，直到找到第一个村庄 k，使得前 k 个村庄的人口权重之和 。此时，a[k] 就是最优的会议点位置 x。
步骤4：计算最小总路程
将 x 代入总路程公式，计算所有村庄到 x 的加权距离之和。
T4：
本题AC代码：
#include<bits/stdc++.h>
using namespace std;
struct node {
int a, b;
};
node f[100005];
bool cmp(node n1, node n2) {
if (n1.a != n2.a) return n1.a < n2.a;
return n1.b > n2.b;
}
int main() {
int n, cnt = 1;
long long ans1 = -0x3f3f3f3f, ans2 = -0x3f3f3f3f;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> f[i].a >> f[i].b;
}
sort(f + 1, f + n + 1, cmp);
for (int i = 2; i <= n; i++) {
if (f[i].a <= f[cnt].b) {
f[cnt].b = max(f[cnt].b, f[i].b);
} else {
f[++cnt] = f[i];
}
}
for (int i = 1; i <= cnt; i++) {
ans1 = max(ans1, (long long)f[i].b – f[i].a);
}
for (int i = 2; i <= cnt; i++) {
long long tmp = (long long)f[i].a – f[i-1].b;
ans2 = max(ans2, tmp);
}
if(ans2<0)ans2=0;
cout << ans2 << " " << ans1 << endl;
return 0;
}
本题思路：
该问题需要计算在多个守卫工作时间段的覆盖下，最长连续无人和最长连续有人的时间段。关键在于将多个时间段合并并找到其中的间隔。
T5：
本题AC代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
struct node{
ll a[4][4]={};
};
node mul(node n1,node n2){
node ans;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
ll tmp=0;
for(int k=1;k<=3;k++){
tmp=(tmp+n1.a[i][k]*n2.a[k][j])%mod;
}
ans.a[i][j]=tmp;
}
}
return ans;
}
node quick(node a,ll n){
node ans;
for(int i=1;i<=3;i++){
ans.a[i][i]=1;
}
while(n){
if(n%2)ans=mul(ans,a);
n/=2;
a=mul(a,a);
}
return ans;
}
int main() {
ll n;
cin>>n;
node A;
A.a[1][1]=1;
A.a[1][2]=1;
A.a[1][3]=1;
A.a[2][1]=0;
A.a[2][2]=1;
A.a[2][3]=1;
A.a[3][1]=1;
A.a[3][2]=0;
A.a[3][3]=1;
node ans=quick(A,n-1);
ll sum=0;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
sum=(sum+ans.a[i][j])%mod;
}
}
cout<<sum;
return 0;
}
本题思路：
这是一个典型的动态规划问题，可以通过状态转移来计数。定义 dp[i][c] 表示长度为 i 的字符串，最后一个字符是 c 时的方案数。
T6：
暂无题解。
附录：
作者之前的文章：
day1：https://blog.csdn.net/Matthew_zhu_/article/details/158290602?spm=1001.2014.3001.5501
day2：https://blog.csdn.net/Matthew_zhu_/article/details/158320728?spm=1001.2014.3001.5501
day3：https://blog.csdn.net/Matthew_zhu_/article/details/158355986?spm=1001.2014.3001.5501
day4：https://blog.csdn.net/Matthew_zhu_/article/details/158391223?spm=1001.2014.3001.5501
day5：https://blog.csdn.net/Matthew_zhu_/article/details/158431065?spm=1001.2014.3001.5501
day6：https://blog.csdn.net/Matthew_zhu_/article/details/158466943?spm=1001.2014.3001.5501
