hdu 多校赛 第六场
slove 2/12
rank 358
补题 5/10
---------------------------------------------------
link
6635 Nonsense Time
每次加入一个数字后求最长上升子序列长度
题目保证数据随机生成，就是说只有 
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
using namespace std;
int n, t;
int a[50005], b[50005];
bool vis[50005];
bool lis[50005];
int num[50005];
int ans;
int res[50005];
int c[50005];
int lowbit(int k)
{
return k & (-k);
}
void update(int k, int x)
{
while (k <= n)
{
c[k] = max(c[k], x);
k += lowbit(k);
}
}
int query(int k)
{
int ans = 0;
while (k)
{
ans = max(ans, c[k]);
k -= lowbit(k);
}
return ans;
}
void find()
{
ans = 0;
memset(c, 0, sizeof(int) * (n + 1));
for (int i = 1; i <= n; i++)
lis[i] = false;
for (int i = 1; i <= n; i++)
num[i] = 0;
for (int i = 1; i <= n; i++)
{
if (vis[i] == true)
continue;
int val = query(a[i] - 1) + 1;
ans = max(ans, val);
num[i] = val;
update(a[i], val);
}
int val = ans;
for (int i = n; i >= 1; i--)
{
if (num[i] == val)
{
lis[i] = true;
val--;
if (!val)
break;
}
}
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
sc("%d", &n);
for (int i = 1; i <= n; i++)
{
vis[i] = false;
sc("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
sc("%d", &b[i]);
find();
res[n] = ans;
for (int i = n; i > 1; i--)
{
vis[b[i]] = true;
if (lis[b[i]] == true)
find();
res[i - 1] = ans;
}
for (int i = 1; i <= n; i++)
printf("%d%c", res[i], i == n ? '\n' : ' ');
}
} 6638 Snowy Smile
区间最大子段和
https://blog.csdn.net/qq_41608020/article/details/98845958
6639 Faraway
给你n个士兵的xi,yi,ki,ti,满足题目中给出的方程
(|xi-xe|+|yi-ye|) mod ki=ti.
求有多少个(xe,ye)满足这n个方程
首先想到去绝对值,有绝对值肯定是不好算的.
n个士兵将平面分为了n^2个块
对于每一块内暴力计算.
由于k只能为2,3,4,5,所以只需要枚举每一块内的60个(其实可以更小)即可,
后面的和%60后的答案是一样的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e2+5;
ll n,m,x[MAX],y[MAX],k[MAX],t[MAX];
vector<ll> list1,list2;
bool check(ll X,ll Y){
for(int i=1;i<=n;++i)
if((abs(x[i]-X)+abs(y[i]-Y))%k[i]!=t[i])
return false;
return true;
}
ll calc(ll a,ll b){
return (b-a-1)<0?0:(b-a-1)/60+1;
}
void solve(){
int T;
scanf("%d",&T);
while(T--){
list1.clear(); list2.clear();
scanf("%lld%lld",&n,&m);
list1.emplace_back(0);
list1.emplace_back(m+1);
list2.emplace_back(0);
list2.emplace_back(m+1);
for(int i=1;i<=n;++i){
scanf("%lld%lld%lld%lld",&x[i],&y[i],&k[i],&t[i]);
list1.emplace_back(x[i]);
list2.emplace_back(y[i]);
}
sort(list1.begin(),list1.end());
sort(list2.begin(),list2.end());
ll ans=0;
for(int i=0;i<list1.size()-1;++i)
if(list1[i]<list1[i+1])
for(int j=0;j<list2.size()-1;++j)
if(list2[j]<list2[j+1])
for(ll k1=0;k1<60;++k1)
for(ll k2=0;k2<60;++k2)
if(check(list1[i]+k1,list2[j]+k2))
ans+=calc(list1[i]+k1,list1[i+1])*calc(list2[j]+k2,list2[j+1]);
printf("%lld\n",ans);
}
}
int main(void)
{
solve();
return 0;
} 6641 TDL
给两个数字 m，k，
已知 m 的范围小于100，所以 
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2005;
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll f(ll n, int m)
{
for (ll i = n + 1; true; i++)
{
if (gcd(n, i) == 1)
{
m--;
if (m == 0)
return i;
}
}
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ll k;
int m;
sc("%lld%d", &k, &m);
ll ans = 2e18;
for (ll i = 0; i <= 1000; i++)
{
ll fn = i;
ll n = k ^ i;
if (n == 0)
continue;
if (f(n, m) - n == fn)
{
ans = min(ans, n);
}
}
if (ans == 2e18)
ans = -1;
pr("%lld\n", ans);
}
} 6645 Stay Real
签到，有 n 个结点的完全二叉树，每个点对应一个权值，每次只能取叶子结点，两个人在树上取数，求两个人取的数的大小。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2005;
bool vis[100005];
ll h[100005];
auto cmp = [](int q, int w) {
return h[q] < h[w];
};
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
{
sc("%lld", &h[i]);
vis[i] = false;
}
vis[n + 1] = true;
priority_queue<int, vector<int>, decltype(cmp)>q(cmp);
for (int i = n; i >= 1; i--)
if (i * 2 > n)
q.push(i);
int op = 0;
ll ans1 = 0, ans2 = 0;
while (!q.empty())
{
int t = q.top();
q.pop();
vis[t] = true;
int fa = t / 2;
while (fa)
{
if (vis[2 * fa] == true && vis[2 * fa + 1] == true)
{
q.push(fa);
fa /= 2;
}
else
break;
}
if (!op)
ans1 += h[t];
else
ans2 += h[t];
op ^= 1;
}
printf("%lld %lld\n", ans1, ans2);
}
}
Momenta公司福利 297人发布