题意：要做n道题，每道题花费时间a[i],但是只有几个时间段可以提交，问最早什么时间可以完成。
思路：直接计算做完全部的题目所花费的时间，然后找到可以提交的时间段，和左端取最大值，就能得出结果。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a,sum;
pair<int,int>p[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a,sum+=a;
cin>>m;
for(int i=1;i<=m;i++){
cin>>p[i].first>>p[i].second;
if(sum<=p[i].second){
cout<<max(p[i].first,sum)<<'\n';
return 0;
}
}
cout<<-1<<'\n';
return 0;
}
题意：n = ax + by，n为不幸年份，在l到r年份最长的连续幸运年份多长
思路：直接枚举x，y，求出所有不幸年份，再作差，注意要用 while ( r / x >= a[lena-1])，而不是while（r>=a[lena-1]*x) 这样会超出long long的范围。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100;
vector <LL> v;
LL a[N], b[N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
LL x, y, l, r, lena, lenb;
cin >> x >> y >> l >> r;
a[0] = b[0] = 1;
lena = lenb = 1;
while ( r / x >= a[lena-1])
{
a[lena] = a[lena-1] * x;
lena++;
}
while ( r / y >= b[lenb-1] )
{
b[lenb] = b[lenb-1] * y;
lenb++;
}
v.clear();
for (int i = 0; i < lena; i++)
for (int j = 0; j < lenb; j++)
if (a[i] + b[j] >= l && a[i] + b[j] <= r)
v.push_back( a[i] + b[j] );
sort (v.begin(), v.end());
LL ans = 0;
if (!v.size()) ans = r - l + 1;
else
{
ans = max(v[0] - l, r - v[v.size() - 1]);
for (int i = 1; i < v.size(); i++)
ans = max(ans, v[i] - v[i - 1] - 1);
}
cout << ans << endl;
return 0;
}
题意：Alice 和 Bob 玩游戏，在一棵树上，Alice 在1节点，Bob在x节点上，Alice追上Bob游戏结束，Alice要让这段过程的步数尽可能的短， Bob 要让这一过程的步数尽可能的长，他们每一步可以选择移动一个节点，或者原地不动，求这段过程的步数是多少？
思路：既然Bob想让步数尽可能大，那么可以让Bob先手，Bob无路可走时就原地不动等待Alice追上他，当Alice追上Bob时，总步数就是Alice步数的两倍，并且当Alice追上Bob时，Alice经过的节点数一定大于Bob。可以用两次DFS求出两人到树上任意一点的步数step1，step2，再枚举每一点，当step2>step1时，求2*step1的最值，得出结果。
点击查看代码
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int vis1[N],vis2[N];
vector<int> p[N];
int step1[N],step2[N]; //记录到某个点的步数
void dfs1(int x,int count){
step1[x]=count;
vis1[x]=1;
for(int i=0;i<p[x].size();i++){
if(vis1[p[x][i]]==0){
count++;
dfs1(p[x][i],count);
count--;
}
}
return ;
}
void dfs2(int x,int count){
step2[x]=count;
vis2[x]=1;
for(int i=0;i<p[x].size();i++){
if(vis2[p[x][i]]==0){
count++;
dfs2(p[x][i],count);
count--; //步数回溯
}
}
return ;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,x,a,b;
cin>>n>>x;
for(int i=0;i<n-1;i++){
cin>>a>>b;
p[a].push_back(b);
p[b].push_back(a);
}
dfs1(1,0); dfs2(x,0);
int sum=0;
for(int i=1;i<=n;i++){
if(step1[i]>step2[i]) //找step1[i]>step2[i],枚举相遇的点
sum=max(sum,2*step1[i]);
}
cout<<sum<<endl;
return 0;
}
D. Two Melodies待更新
E. Army Creation难度过高，暂不更新
F. Bipartite Checking难度过高，暂不更新