第一个
这道题我是真想了半天 后面还是没想出来 哪知道是dp啊！！！
然后这个就很像背包了 不同的是第二层是直接枚举约数装进去 写法上也很讲究 我指的是初始化 没有初始化！只有边做边初初始化 为什么呢 因为对于所有的数而言 是取max 然后加上本身 如果一开始所有人都是 做的时候取max是啥意思！ 对吧
所以我们只需要写个On\(\sqrt{n}\)的程序
点击查看代码
sort(a + 1, a + 1 + n);
if(a[i]%j==0)
{
if(j==1)add=dp[a[i]/(a[i]/j)];
else
add=max(max(add,dp[a[i]/(a[i]/j)]),dp[a[i]/j]);
cout<<j<<" "<<add<<endl;
}
这就是为什么dpa[i]为什么后面++
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= a[i]; j++) {
if (a[i] % j == 0) {
dp[a[i]] = max(max(dp[a[i]], dp[a[i] / (a[i] / j)]), dp[a[i] / j]);
}
}
dp[a[i]] ++;
ans = min(ans, n - dp[a[i]]);
}
但是！ 时间还可以优化 联想埃氏筛 对于任何一个数 可以构成倍数的化 它只对自己的倍数产生贡献于是 我们就可以写一个ONlogN的代码
给这样一个代码
for (int i = 1; i <= 2e5 + 10; i++) {
for (int j = i + i; j <= 2e5 + 10; j += i) {
// 内层循环体
}
}
外层循环2e5 我10下面都不打了 我当时随便写的
内层分析
减1是减去初始的比如我们当i=2时 0一直加到2e5 是2e5/2
i=1：2e5/1-1
i=2:2e5/2-1
i=3:2e5/3-1
i=k:2e5/k-1
于是得出\(\sum\limits_{i=1}^n\dfrac{2e5}{i}-1\)
把2e5拖出来 里面就是一个调和级数的表达式
Hn=\(\sum\limits_{i=1}^n\dfrac{1}{k}\)=\(ln(n)+0.577\)
那个0.577直接省略
再来说下为什么老是明明是ln又变成log
\(lnx\)=\(loge^X\)=\(\dfrac{log2^x}{log2^e}\)
所以\(lnx\)=\(log2^X*loge^2\)
后面那个是常数直接不管了
所以回到上面
这个的时间复杂度就是ONlnN
然后直接变成Onlogn了 没区别的其实 对于复杂度没区别
不过埃氏筛氏是基于质数的调和级数 多一个log
回到原题
那么代码就可以动手写了 注意这里是随机给数据 所以我们必须要从1-n枚举 而不是1-n 枚举Ai 否则n个2的数据可以给我们卡的天上去
点击查看代码
for(int i=1;i<=2e5;i++)
{
dp[i]+=cnt[i];
//cout<<dp[i]<<endl;
for(int j=i+i;j<=2e5;j+=i)
{
dp[j]=max(dp[j],dp[i]);
}
ans=max(ans,dp[i]);
}
第二个
一开始想多了 后面反应过来了 把他的抢了 浮上来的对方队头也需要考虑对方对头元素 然后对比损失 结果这个式子一些出来就发现抢掉对方的一定是最优的 于是就ac了
一开始想多了 。。没想到这题这么简单
写错的
第三个非常好的一道题
题意简述下
给你ai bi 找到一个j满足
ai>aj bi>bj
或者ai>bj bi>ai
这题我是真做了半天 也没做出来
我一开始用线段树存值 发现也是错的 存在逻辑错误 后面想了别的办法 用的数轴表现（也只能输出yes no存不了答案） 再一看数据这么大 好了
我就知道做不出来了
看了下题解
今天早上考物理 物理卷子交了张白卷只写了选择上去 然后就在等提前交卷时间 在那默写这个代码 因为昨晚看的题解 看完以后 有点抵触
于是不想动手写 看b站去了
这个代码早上默写了一遍 一考完就去机房打出来了 唯一不同的是我默写时候 我以为这个maxn是按从大到小排序的 自己试了下发现从小到大比较合适
这个代码非常好 简直堪比Money Trees那道题
点赞！
点击查看代码
struct node {
int mini;
int maxn;
int id;
} a[range];
bool cmp(node x,node y)
{
if(x.maxn==y.maxn)return x.mini<y.mini;
return x.maxn<y.maxn;
}
struct Node{
int id;
int num;
}ans[range];
bool ccmp(Node x,Node y){return x.id<y.id;}
int num;
void init()
{
for(int i=1;i<=n;i++)
{
ans[i]={0,0};
a[i]={0,0,0};
}
}
void solve() {
cin >> n;
num=0;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
a[i].maxn = max(x, y);
a[i].mini = min(x, y);
a[i].id = i;
ans[i].id=i;
ans[i].num=-1;
}
sort(a+1,a+1+n,cmp);
int mini=1e9;
for(int i=1,t=i+1;i<=n;i=t)
{
while(a[i].maxn==a[t].maxn&&t<=n)t++;
for(int j=i;j<=t-1;j++)
{
if(a[j].mini>mini)
{
ans[a[j].id].num=num;
}
}
for(int j=i;j<=t-1;j++)
{
if(a[j].mini<mini)
{
mini=a[j].mini;
num=a[j].id;
}
}
}
sort(ans+1,ans+1+n,ccmp);
for(int i=1;i<=n;i++)
cout<<ans[i].num<<" ";
cout<<endl;
}
第四个
个人认为这题暴力做法比我的优化更难想 竟然是直接枚举前面的sum然后直接看能不能匹配 然后做的 这个只能说艺高人胆大了 我看了数据也没想出 \(On^2\)的做法
第五个
这道题是我自己想出来的
一开始读错了题 以为互相都要相交 我这当时想了40多分钟吧 真的想不下去了 这哪里能做啊 然后我就再读了下题 反正。。。。
服辣 于是重新思考 然后又想了下发现对右端点排序再二分查找 是很难实现的 我于是想了下 直接把左边整理好 右边也整理好 直接二分
有点像之前做的那个题目
题目
这题给了我一点小启示 于是我直接二分 然后二分的对象选举很重要
假设此时枚举到的人左边是st 右边是fin
我们要找的人他的右边比st大，但是左边比fin小
记住这句话
于是对于样例
4
1 2
2 3
3 5
4 5
整理成
L：1 2 3 3 4
R：4 5 5 8 8
然后我们假设此时枚举到了3 5 也就是第三个人
我们发现可以找到L是4 R是1 看来我们可以找到3个人和他一个集合 你可能会有疑问
这里的L R不匹配啊这是排序了的 你怎么能保证相互对应呢
这边你要明白 对于找比fin小的
在L数组 我们是看1-flagL
对于找比st大的R数组 我们的元素选取是flagR-n
我们不用管 是不是相互对应 因为Li必须小于Ri 找到了一个Li 他对于的Ri肯定是可以在flagr-n之间的 因为你Li可以找到别fin小 就一定可以相交对吧 那你的Ri肯定大于Li 那么你肯定指针flagR肯定是在flagL之前的
因为你想想st比fin小 那fin指针肯定指后面的 因为我们fin是找左数组的 肯定是可以走的更远的 对于右数组而言找一个比st大的那肯定可以在他之前找到 毕竟你想st又小又处于一个最大的R数组里
肯定不会出现那种相离的状态就是flagL<flagR这种可能的 我也没特判这种可能 直接ac 因为我知道不可能出现 最差的情况就是自己指自己也有一个贡献
这就是我做题的思路 没看题解上面思路 因为写出来的代码都差不多
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug cout<<endl<<"----------"<<endl;
using namespace std;
const int range=3e5+10;
int n;
pair<int,int>p[range];
//无语住了 读题读错了 读成任何一条边互相都相交
//给我想了半天都没想出来 回头一看题 读错了
//正解一会就想出来了 之前想了半天半天都没想出来
//心里还想这尼玛能做的啊
//bool cmp(pair<int,int>a,pair<int,int>b)
//{
// if(a.second==b.second)return a.first<b.second;
// return a.second<b.second;
//}
int a[range];
int b[range];
void init()
{
for(int i=1;i<=n+100;i++){
a[i]=b[i]=0;
p[i]={0,0};
}
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].first>>p[i].second;
a[i]=p[i].first;
b[i]=p[i].second;
}
int ans=1e7;
sort(a+1,a+1+n);sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
int st=p[i].first;
int fin=p[i].second;
int x=upper_bound(a+1,a+1+n,fin)-a;
int y=lower_bound(b+1,b+1+n,st)-b;
if(a[x]>fin)x--;
if(x==n+1)x--;
if(y==n+1)y--;
if(x<y)continue;
int h=x-y+1;
// debug
// cout<<st<<" "<<fin<<endl;
// cout<<x<<" "<<y<<endl;
ans=min(n-h,ans);
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
最后
写完了
早点回去今天 因为今天早上一考完回宿舍了下 就来了 今天早十几分种下班了 回宿舍洗澡 看看下雨了没 跑步啥的
标签：int,小结,代码,st,枚举,2e5,fin From： https://www.cnblogs.com/LteShuai/p/18286582