Sum
我们发现只有两个两个合成才会使价值更大,然后取反用哈夫曼树构建得解
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e5 + 10,M = 3e5 + 10,mod = 1e7 + 7;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
//#define x first
//#define y second
void solve()
{
priority_queue<int,vector<int>,greater<int>>q;
int n;cin >> n;
for(int i = 0; i < n; i ++)
{
int x; cin>> x;
x = -x;
q.push(x);
}
int sum = 0;
while(q.size() > 1)
{
int a = q.top();q.pop();
int b = q.top();q.pop();
if(a + b > 0)break;
sum = (sum + a + b) % mod;
q.push(a + b);
}
cout << - sum << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
考察差分,我们用s[i]表示包含i的最大价值
例如:
1 3 30
2 3 50
则s[3] = 80
那么怎样得到这样一个数组呢?
可以采用区间加,于是想到了差分
然后我们枚举去掉那个数才能使得价值最大
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e6 + 10,M = 3e5 + 10,mod = 1e7 + 7;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
//#define x first
//#define y second
int n,m;
int c[N];
void solve()
{
int sum = 0;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
int l,r,w;cin >> l >> r >> w;
c[l] += w,c[r + 1] -= w;
sum += w;
}
int res = 0;
for(int i = 1; i <= m; i ++)
{
//得到当前位置的数
c[i] += c[i - 1];
res = max(res, sum - c[i]);
}
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
将每一个时间转化成分钟,那么就可以看成是很多段区间了
问题就转化成了问我们一个数是否在我们给定的区间内
区间合并+二分
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
const int N = 1e3 + 10,INF = 1e18;
typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
PII e[N],ans[N];
int cnt;
void solve()
{
int n,h,m,q;cin >> n >> h >> m >> q;
for(int i = 1; i <= n; i ++)
{
int a,b,c,d;cin >> a >> b >> c >> d;
e[i] = {a * m + b,c * m + d};
}
sort(e + 1,e + 1 + n);
//区间合并,为后面的二分区间做准备,使其满足单调性
int st = e[1].x,ed = e[1].y;//这样写的好处是不用特判边界
for(int i = 2; i <= n; i ++)
{
if(e[i].x <= ed) ed = max(ed, e[i].y);//合并
else //不能合并开新组
{
ans[++ cnt] = {st, ed};
st = e[i].x,ed = e[i].y;
}
}
//将最后一个加进来
ans[++ cnt] = {st, ed};
while(q --)
{
int a,b;cin >> a >> b;
int t = a * m + b;
int l = 0,r = cnt;
//ans[0] = {-INF,-INF};
//ans[cnt + 1] = {INF,INF};
//二分出来最大的一个小于等于t的位置,这样才能保证r是最大的满足要求的位置
while(l < r)
{
int mid = l + r + 1 >> 1;
if(ans[mid].x <= t)l = mid;
else r = mid - 1;
}
if(t >= ans[l].x && t <= ans[l].y)cout << "No" << endl;
else cout << "Yes" << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#define int long long
const int N = 2010,M = N * N;
typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int n,m;
char s[N][N];
int h[N],e[M],ne[M],idx;
int pre[N],dist[N];
int check(char s1[],char s2[])
{
int dif = 0;
for(int i = 0; i < m; i ++)
dif += s1[i] != s2[i];
return dif;
}
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
int bfs()
{
memset(dist, 0x3f, sizeof dist);
dist[n + 2] = 0;
queue<int>q;
q.push(n + 2);
while(!q.empty())
{
int t = q.front();
q.pop();
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
pre[j] = t;
q.push(j);
}
}
}
if(dist[n + 1] == 0x3f3f3f3f)return -1;
return dist[n + 1] - 1;
}
void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= n + 2; i ++)
cin >> s[i];
for(int i = 1; i <= n + 2; i ++)
for(int j = i + 1; j <= n + 2; j ++)
if(check(s[i],s[j]) <= 1){
add(i,j),add(j,i);
}
int t = bfs();
if(t != -1)
{
cout << t << endl;
int ed = n + 1;
while(pre[ed] != n + 2)
{
cout << s[ed] << endl;
ed = pre[ed];
}
cout << s[ed] << endl << s[n + 2] << endl;
}
else cout << t << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}
Slash
状态表示:f[i,j,k]表示以矩阵的(i,j)结尾,当前最新字符串匹配了s串的前k位时,完整匹配了多少个字符
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#define int long long
const int N = 110,M = N * N,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int f[N][N][N];
char a[N][N],s[N];
int n,m;
void solve()
{
cin >> n >> m;
cin >> s + 1;
int len = strlen(s + 1);
for(int i = 1; i <= n; i ++)scanf("%s",&a[i][1]);
memset(f, -0x3f, sizeof f);
f[0][1][0] = 0;
for(int i = 1;i <= n; i ++)
for(int j = 1; j <= m; j ++){
//相等的情况更新f[i][j][k]
for(int k = 1; k <= len; k ++)
if(s[k] == a[i][j])
f[i][j][k] = max(f[i - 1][j][k - 1],f[i][j - 1][k - 1]);
f[i][j][0] = f[i][j][len] + 1;//换了一下
//不等的情况更新f[i][j][0]
for(int k = 0; k <= len; k ++)
f[i][j][0] = max(f[i][j][0],max(f[i - 1][j][k],f[i][j - 1][k]));
}
int res = 0;
for(int i = 0;i <= len; i ++)
res = max(res, f[n][m][i]);
cout << res << endl;
}
signed main()
{
//ios::sync_with_stdio(0), cin.tie(0);
// int t;cin >> t;
// while(t --)
// {
// solve();
// }
solve();
return 0;
}