7/24 训练日志

D2. Chopping Carrots (Hard Version)
1.枚举极小值，其值存在上限，为数组a中最小的那个数，即为a[1]；
2.无法如D1一般枚举a[i]，数据范围改变，存在超时问题；
3.可改变思路：枚举p[i],范围是1~k。a[i]数组是单调不减的，根据极差值，可构造a[i]/p[i],使得大小存在递增关系；
4.通过枚举极差中的最小值，再枚举每一个p，再通过lower_bound查找数组a中的值；
5.若正好存在i*p==a[i]，则找到；若大于数组a中最大值，则跳出；

#include 
#define int long long
#define endl 'n'

using namespace std;
const int N=1e6+5;
int n,k,a[N];

signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int mn=a[1],mx=a[n],ans=1e9;
        for(int i=1;i<=mn;i++)
        {
            int res=0;
            for(int j=1;j
                int ai=i*(j+1);
                if(ai-i>mx)
                    break;
                int g=lower_bound(a+1,a+n+1,ai)-a-1;
                if(!g||a[g]=i*k)
                res=max(res,a[n]/k);
            if(res>=i)
                ans=min(ans,res-i);
        }
        cout< 
思维 
C. Recover an RBS
 题意并不难理解，但思路也没那么好想。
 三种符号'(' ')' '?'，可想到左右括号是可以相互抵消的，而？是存在其中的变量。要用？来表示左右括号中较少的那个来达到平衡。确定的状态可进行消去，不确定的要进行保留，最后比较是否相等。
 
#include 
#define int long long
#define endl 'n'

using namespace std;
const int N=1e6+5;
string s;

signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>s;
        int a=0,b=0;
        for(int i=0;i
            if(s[i]=='?')
                b++;
            else if(s[i]=='(')
                a++;
            else if(s[i]==')')
                a--;
            if(a<0)
                a++,b--;
            if(a==0&&b==1)
                a++,b--;
        }
        if(abs(a)==b)
            cout<<"YES"< 
C. Mark and His Unfinished Essay 
1.若用暴力截取字符串的方法肯定会超时。
 2.用l[i]和r[i]记录每次添加区间的左端点和右端点；用tl[i]和tr[i]记录，将截取子串添加主串中时，左右端点值；
 3.从后向前，用每次询问的x减去区间长度，最后锁定下标x在字符串中的位置。tl[i]-l[i]可知该段区间长度
 
#include 
#define int long long
#define endl 'n'
#define IOS ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=1e6+100;
int n,c,q,l[N],r[N],tl[N],tr[N];
string s;
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>c>>q;
        cin>>s;
        tl[0]=0,tr[0]=n;
        for(int i=1;i<=c;i++)
        {
            cin>>l[i]>>r[i];
            tl[i]=tr[i-1]+1;
            tr[i]=tl[i]+(r[i]-l[i]+1)-1;
        }
        while(q--)
        {
            int x;cin>>x;
            for(int i=c;i>=1;i--)
                if(tl[i]<=x&&x<=tr[i])
                    x-=tl[i]-l[i];
            cout< 
算法训练 
牛客练习赛62 水灾 
一句话题意：给一个 n 个节点 m 条带权边的无向连通图，有 q 次询问，每次询问图中 ki 个互不相同的点，选择一个数 x，然后将图中所有边权小于等于 x 的边删除。求当删除这些边后 ki 个点互不连通时，x 的最小值。
 
思路：
 1.将小于等于x的边删除，x最小为多少=>可看出建立kruskral重构树将边权化为点权，建立最大生成树，从而建立出小根堆。
 2.两个点的最近公共祖先删除，则两个点不再联通；即根据二叉树的性质，可知找出数组a中最大的子树根节点即可。
 3.此时kruskal的每个子树是原图上保留边权不小于根节点权值的边(即为小根堆)后的极大连通子图。
 —>对于询问时数组a中的值，若是暴力两两比较求lca得最大值会超时；
 因此利用小根堆性质，相邻节点(在同一层)上节点比较，可得出最大值，复杂度O(K）
 
#include 
#define int long long
#define endl 'n'
#define IOS ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
const int N=1e6+100;
int n,m,q,a[N],f[N],tol,val[N],lev[N],level,tmp[N],lans;
vectorg[N];
bool vis[N];
struct node
{
    int x,y,z;
}e[N];
bool cmp(node e1,node e2)
{
    return e1.z>e2.z;
}
int r_find(int r)
{
    if(r==f[r])    return f[r];
    f[r]=r_find(f[r]);
    return f[r];
}
int siz[N],dep[N],son[N],fa[N],top[N];
void dfs1(int u,int pare)   //重构树lca初始化
{
    siz[u]=1;dep[u]=dep[pare]+1;
    son[u]=0;fa[u]=pare;
    lev[u]=++level;
    for(auto &v:g[u])
    {
        if(v!=pare)
        {
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[son[u]]
    top[u]=topf;
    if(son[u])
        dfs2(son[u],topf);
    for(auto &v:g[u])
    {
        if(v!=fa[u]&&v!=son[u])
            dfs2(v,v);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]
    for(int i=1;i
        int fx=r_find(e[i].x),fy=r_find(e[i].y);
        if(fx!=fy)
        {
            val[++tol]=e[i].z;
            f[fx]=f[fy]=tol;
            //g[fx].push_back(tol);
            g[tol].push_back(fx);
            //g[fy].push_back(tol);
            g[tol].push_back(fy);
            if(tol ==n*2-1) break;
        }
    }
    for(int i=1;i<=tol;i++)
    {
        if(!siz[i])
        {
            int rt=r_find(i);
            dfs1(rt,0);
            dfs2(rt,rt);
        }
    }
}
bool cmp1(int a,int b){return lev[a]
    IOS;
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
        cin>>e[i].x>>e[i].y>>e[i].z;
    kruskal();
    while(q--)
    {
        int ans=0;
        int k;cin>>k;
        for(int i=1;i<=k;i++)
            cin>>tmp[i],tmp[i]^=lans;
        sort(tmp+1,tmp+k+1,cmp1);
        for(int i=2;i<=k;i++)
            ans=max(ans,val[lca(tmp[i],tmp[i-1])]);
        cout< 
P1776 宝物筛选 
直接套用模板会超时，可观察到件数达到1e5次方，因此使用二进制差分转化为01背包
 
#include 

using namespace std;
const int maxn=1e5+5;
int n,w,v[maxn],c[maxn],f[maxn];

int main()
{
    int cnt=1;
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++)    
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z); 
        int t=1;
        while(z>=t)
        {
           v[cnt]=x*t;
           c[cnt++]=y*t;
           z-=t;
           t<<=1;
        }
        if(z)
        {
            v[cnt]=x*z;
            c[cnt++]=y*z;
        }
    }
    cnt--;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=w;j>=c[i];j--)
        {
            f[j]=max(f[j],f[j-c[i]]+v[i]);
        }
    }
    cout<