Codeforces 960 二进制构造子序列 完全二叉树shift模拟 主席树/MAP DP
2024-08-31 01:54:54
A
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 0x3f3f3f3f
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { , }, { , -}, { -, }};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
int main()
{
string f;
cin >> f;
int len = f.size();
int flag = ;
int numa = ;
int numb = ;
int numc = ;
int now = ;
for (int i = ; i < len; i++)
{
if (f[i] - 'a' < now)
{
flag = ;
break;
}
else
{
now = max(now, f[i] - 'a');
}
}
if (!flag)
{
cout << "NO" << endl;
return ;
}
for (int i = ; i < len; i++)
{
if (f[i] == 'a')
{
numa++;
}
else if (f[i] == 'b')
{
numb++;
}
else
{
numc++;
}
}
if (numa < || numb < )
{
cout << "NO" << endl;
return ;
}
if (numc == numa || numc == numb)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
B
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 0x3f3f3f3f
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { , }, { , -}, { -, }};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
priority_queue<ll, vector<ll>, less<ll>> que;
ll a[];
ll b[];
int main()
{
ll anser = ;
ll n, k1, k2;
cin >> n >> k1 >> k2;
for (int i = ; i <= n; i++)
{
scanf("%lld", &a[i]);
}
for (int i = ; i <= n; i++)
{
scanf("%lld", &b[i]);
que.push(abs(a[i] - b[i]));
anser += abs(a[i] - b[i]) * abs(a[i] - b[i]);
}
int cur = k1 + k2;
while (cur)
{
ll now = que.top();
que.pop();
if (now == )
{
cur--;
que.push();
anser += ;
}
else
{
cur--;
que.push(now - );
anser -= 1LL * now * now;
anser += 1LL * (now - ) * (now - );
}
}
cout << anser << endl;
}
C
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 0x3f3f3f3f
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { , }, { , -}, { -, }};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
priority_queue<ll, vector<ll>, less<ll>> que;
vector<ll> ans;
int main()
{
//freopen("out.txt","w",stdout);
ll x, d;
cin >> x >> d;
// if(x<=10000)
// {
// for(ll i=1;x;i+=d+1)
// {
// cout<<i<<" ";
// x--;
// }
// return 0;
// }
ll cur = ;
if (x == )
{
cout << << endl;
cout << << endl;
return ;
}
if (x & )
{
ans.push_back(1e17 - );
x -= ;
}
for (ll i = ; i <= ; i++)
{
if ((1LL << i)&x)
{
que.push(i);
}
}
while (!que.empty())
{
ll number = que.top();
que.pop();
for (ll i = ; i <= number; i++)
{
ans.push_back(cur);
}
cur += d;
ans.push_back(cur);
cur += d;
}
cout << ans.size() << endl;
for (ll ch : ans)
{
cout << ch << " ";
}
}
D
给你一个完全二叉树有三种操作
1.把值为X的节点所在当前层 移动K次
2.把值为X的节点所在当前层 移动K次 子树也跟着移动
3.询问你值为X所在结点到根节点路径上节点的值
shift[i]表示第i层移动的次数
第二个操作很好处理 第三个操作就是在第二个操作上pushdown 下一层移动的次数是上一层的两倍
(记得取模操作)
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 0x3f3f3f3f
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { , }, { , -}, { -, }};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
int Q;
int T;
ll level;
ll X, K;
ll lenth, position;
ll shift[];
void update(ll x, ll K)
{
shift[x] += K;
shift[x] %= (1LL << (x - ));
}
void pushdown(ll x, ll K)
{
shift[x] += K;
shift[x] %= (1LL << (x - ));
if (x + < )
{
K = (K << );
pushdown(x + , K);
}
}
ll getpos(ll level, ll x)
{
ll l = 1LL << (level - );
ll r = (1LL << level) - ;
ll now = x + shift[level];
if (l <= now && now <= r)
{
return now;
}
if (now < l)
{
ll cha = l - now - ;
return r - cha;
}
else
{
ll cha = now - r - ;
return l + cha;
}
}
void print(ll level, ll pos)
{
if (level == )
{
cout << ;
return ;
}
ll now = pos - shift[level];
ll l = 1LL << (level - );
ll r = (1LL << level) - ;
if (l <= now && now <= r)
{
cout << now << " ";
print(level - , pos / );
return;
}
if (now < l)
{
ll cha = l - now - ;
cout << r - cha << " ";
}
else
{
ll cha = now - r - ;
cout << l + cha << " ";
}
print(level - , pos / );
return ;
}
int main()
{
//freopen("out.txt","w",stdout);
cin >> Q;
while (Q--)
{
int T;
scanf("%d %lld", &T, &X);
for (ll i = ; i >= ; i--)
{
if ((1LL << (i - ))&X)
{
if (((1LL << i)&X) == )
{
level = i;
break;
} }
}
//cout<<level<<" ";
if (T == )
{
scanf("%lld", &K);
if (X == )
{
continue;
}
K %= 1LL << (level - );
update(level, K);
}
else if (T == )
{
scanf("%lld", &K);
if (X == )
{
continue;
}
K %= 1LL << (level - );
pushdown(level, K);
}
else
{
if (X == )
{
cout << << endl;
continue;
}
cout << X << " ";
position = getpos(level, X);
//cout << position;
print(level - , position / );
cout << endl;
}
}
}
E
F
先来做F的简化版
http://codeforces.com/contest/459/problem/E
求有向图的最长严格递增路径
dp[i]表示以第i条边为结尾的最长路径 g[i]表示以i结点为结尾的最长路径
所以dp[i]=dp[edge[i].from]+1即以第i条边结尾的答案是以该边from结尾的最长路径长度+其本身
首先排序 相同大小的边之间是不会相连的
而如果每遍历一条边就g[edge[i].to]=max(g[edge[i].to],dp[i])的话 如果edge[i+1].from=edge[i].to 就变成这两条边相连了所以相同值的边要分处理
复杂度NLOGN
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 300007
using namespace std;
int n, m;
int dp[MAX], g[MAX];
struct Edge
{
int u, v, w;
bool operator < ( const Edge& a ) const
{
return w < a.w;
}
} e[MAX];
int main ( )
{
while ( ~scanf ( "%d%d" , &n , &m ) )
{
for ( int i = ; i < m ; i++ )
{
scanf ( "%d%d%d" , &e[i].u , &e[i].v , &e[i].w );
}
sort ( e , e + m );// 排序
int t = ;
e[m].w = -;//使得最后一组边也能更新
int ans = ; //答案
for ( int i = ; i < m ; i++ ) //从小到大枚举
{
int v = e[i].v;
int u = e[i].u;
int w = e[i].w;
dp[i] = g[e[i].u] + ; //以第i条边结尾的答案是以e[i].from节点为结尾的最长路径+它本身
if ( e[i].w != e[i + ].w )
{
for ( int j = t ; j <= i ; j++ ) //处理相同边
{
g[e[j].v] = max ( g[e[j].v] , dp[j] );//更新e[i].to的答案 以便处理下一组边
}
t = i + ;//重置相同边的起点
}
ans = max ( ans , dp[i] );
}
printf ( "%d\n" , ans );
}
}
现在来做F
如果用上面的方法来做 不能保证下标不能有逆序对这个条件
如果去掉edge[i].from=edge[j].to这个条件的话 这道题就变成一道裸的LIS
如果用来DP的话 普通的dp[i][j]数组表示以i为结尾的权重最大为j的最长递增路径长度 因为i和j都是1e5的会炸
但是用MAP来存的话 因为每个dp[i]表示的都是一个树状数组 每次插入和询问都是LOGN的 所以最多只会涉及到NLOGN个节点 可以接受
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 0x3f3f3f3f
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[][] = {{, }, { , }, { , -}, { -, }};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
const int N = 1e5 + ;
map<int, int> bits[N];
int query(int u, int x)
{
int ans = ;
while (x)
{
ans = max(ans, bits[u][x]);
x -= x & -x;
}
return ans;
}
void update(int u, int x, int v)
{
while (x < N)
{
bits[u][x] = max(bits[u][x], v);
x += x & -x;
}
}
int main()
{
int n, m, u, v, w;
int anser = ;
int cur;
scanf("%d%d", &n, &m);
for (int i = ; i < m; i++)
{
scanf("%d%d%d", &u, &v, &w);
w++;
cur = query(u, w - ) + ;
update(v, w, cur);
anser = max(anser, cur);
}
printf("%d\n", anser);
return ;
}
用主席树来做的话 其实和MAP DP递推是同理的 只建立需要的节点 其他节点忽略
#include<cstdio>
#include<algorithm>
#define lowbit(x) (x&-x)
using namespace std;
const int maxn=;
int n,m,f[maxn],rt[maxn],sz;
struct tree{int l,r,mx;}t[maxn*];
void insert(int& k,int l,int r,int x,int y){
if(!k)k=++sz;t[k].mx=max(t[k].mx,y);
if(l==r)return;
int mid=(l+r)>>;
if(x<=mid)insert(t[k].l,l,mid,x,y);
else insert(t[k].r,mid+,r,x,y);
}
int query(int k,int l,int r,int x){
if(l==r)return t[k].mx;
int mid=(l+r)>>;
if(x<=mid)return query(t[k].l,l,mid,x);
else return max(t[t[k].l].mx,query(t[k].r,mid+,r,x));
}
int main(){
scanf("%d%d",&n,&m);
int ans=;
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
f[i]=query(rt[u],,,w-)+;
insert(rt[v],,,w,f[i]);
ans=max(ans,f[i]);
}
printf("%d",ans);
return ; }
最新文章
- 关于AngularJS（1）
- 个人对JQuery Proxy()函数的理解
- Android中的5种数据存储方式
- GPU---并行计算利器
- Android R文件相关问题
- web双机热备添加心跳检测ip的时候填了网关导致外网ip不能上网
- Android Material Design:NavigationView抽屉导航菜单
- java基础篇---I/O技术
- Python实战（2）
- (转)Tomcat内存设置
- 理解FTP协议
- warning : json_decode(): option JSON_BIGINT_AS_STRING not implemented in xxx
- meta--------link
- SqlCommandBuilder类是如何构建T-Sql语句
- 操作系统-实验一、DOS使用命令实验
- H5+JS+JQuery+ECharts实现异步加载
- python的枚举
- mbstowcs 和ifstream 前为何要setlocale
- python中TCP协议中的粘包问题
- Ubuntu中安装python3.6（转）
热门文章
- 关于Tomcat重启和关闭后重启session变化
- jquery版本轮播图（es5版本，兼容高）
- 【mysql】错误代码1308 Invalid use of NULL value
- Delphi XE2 之 FireMonkey 入门(32) - 数据绑定: TBindingsList: TBindList、TBindPosition [未完成...]
- Python学习之==>第三方模块的安装、模块导入
- Flink容错机制
- oracle ogg 单实例双向-新增表，修改表结构（oracle-oracle
- 【MM系列】SAP MM模块-货物移动对标准价的影响
- Django-DRF组件学习-视图学习
- MyEclipse mac版删除代码崩溃--解决方案