Starry

发表于 更新于 分类于 本文字数： 651 阅读时长 ≈ 2 分钟

题面

首先想到将各个联通块缩成一个点来解决问题，接下来就是考虑将各个联通块经过变换都变为P态：

一个贪心的想法是将连有三个及以上N态点的P态点删去，同时，然后再加上剩下的N态点数就为答案，但贪心做法并不能达到全局最优，如： 

graph TD
1_P-->2_P;
2_P-->3_N;
3_N-->4_P;
3_N-->5_P;
5_P-->6_N;
5_P-->7_N;
4_P-->8_N;
4_P-->9_N;
4_P-->10_N;

贪心做法为4，而正解应该为3

那么我们接下来应该考虑的是每次操作的影响，对于每次操作，都会使该块与相邻联通块合成一个新的整体，所以约束条件应该转到联通块树的最长路径也即树的直径，这样的话。树直径上的点全转为P态时，其余树干的点也均转为P态

而对于树的直径，我们可以两遍dfs来求，参考：树的直径

于是考虑答案的组成情况：

1.路径长度为奇数，即有偶数个点，那么答案便是

2.路径长度为偶数，即有奇数个点，那么我们就需要判断树直径终点或端点状态来加1

于是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const int N = 2e5 + 86;
vector<char> c(N);
bitset<489899> np;
struct No
{
    int to, nxt;
} e[N * 4];
int hd[N*2], tot = 1, cnt = 1, vis[N];
inline void add(int x, int y)
{
    e[++tot] = (No){y, hd[x]};
    hd[x] = tot;
    e[++tot] = (No){x, hd[y]};
    hd[y] = tot;
}

void dfs(int a, int ma)
{
    vis[a] = ma;
    for (int eg = hd[a]; eg; eg = e[eg].nxt)
    {
        if (!vis[e[eg].to] && c[e[eg].to] == c[a])
            dfs(e[eg].to, ma);
    }
}

LL n,max1,dis[N*4],u,v;

void dfss(int now,int fat)
{
	dis[now] = dis[fat] + 1;
	for(int i = hd[now]; i; i = e[i].nxt)
	  if(e[i].to != fat) dfss(e[i].to,now);
}
void get_road(int st)
{
    dis[0]=-1;
	dfss(st,0);
	for(int i = n+5, maxdis = 0; i <= cnt-1; i ++)
	  if(dis[i] > maxdis) u = i,maxdis = dis[i];
	dfss(u,0);
	for(int i = n+5, maxdis = 0; i <= cnt-1; i ++)
	  if(dis[i] > maxdis) v = i,maxdis = dis[i];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    f(i, 1, n) cin >> c[i];
    cnt+=n+4;
    f(i, 1, n - 1)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    f(i, 1, n)
    {
        if (!vis[i])
        {
            dfs(i, cnt++);
            np[vis[i]]=(c[i]=='P');
        }
    }
    map<LL ,map<LL,int> >tr;
    f(i, 1, n)
    {
        for (int eg = hd[i]; eg; eg = e[eg].nxt)
        {
            if (vis[i] != vis[e[eg].to]&&!tr[min(vis[i],vis[e[eg].to])][max(vis[i],vis[e[eg].to])])
            {
                tr[min(vis[i],vis[e[eg].to])][max(vis[i],vis[e[eg].to])]=1;
                add(vis[i],vis[e[eg].to]);
            }
        }
    }
    get_road(vis[1]);
    if(dis[v]&1){
        cout<<((dis[v]+1)>>1);
    }
    else cout<<((dis[v])>>1)+(1^np[v]);
    return 0;
}

发表于 更新于 本文字数： 107 阅读时长 ≈ 1 分钟 

journey
title My working day
section Go to work
  Make tea: 5: Me
  Go upstairs: 3: Me
  Do work: 1: Me, Cat
section Go home
  Go downstairs: 5: Me
  Sit down: 3: Me



sequenceDiagram
Alice->>John: Hello John, how are you?
loop Healthcheck
    John->>John: Fight against hypochondria
end
Note right of John: Rational thoughts!
John-->>Alice: Great!
John->>Bob: How about you?
Bob-->>John: Jolly good!



classDiagram
Class01 <|-- AveryLongClass : Cool
<<interface>> Class01
Class09 --> C2 : Where am i?
Class09 --* C3
Class09 --|> Class07
Class07 : equals()
Class07 : Object[] elementData
Class01 : size()
Class01 : int chimp
Class01 : int gorilla
class Class10 {
  <<service>>
  int id
  size()
}

发表于 更新于 分类于 本文字数： 107 阅读时长 ≈ 1 分钟

第一问是求最长不升子序列，第二问是求最长上升子序列

对于第一问利用vector的反向迭代器来转换为最长不降子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL x;
vi v(1, -1),j(1,-1),s;
int main()
{
    while (scanf("%lld",&x)==1)
    {
        s.pb(x);
        if (x > v.back())
            v.pb(x);
        else
            *lower_bound(all(v), x) = x;
    }
    for(auto it=s.rbegin();it!=s.rend();it++){
        if((*it)>=j.back())
        j.pb(*it);
        else *upper_bound(all(j),*it)=*it;
    }
    cout<<j.size()-1<<"\n";
    cout << v.size()-1;
    return 0;
}

发表于 更新于 分类于 本文字数： 361 阅读时长 ≈ 1 分钟

A题排序然后从l开始由小到大加到不超过最大值即可

B题贪心，但写的烂代码，爆int还tle，看到别人的排序是真帅

D1题是个dp，考虑每个因子的转移，不应该仅想到直接求该数因子，一个考虑遍历方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
LL tt,n,l,r,k;
int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>n>>l>>r>>k;
        vi v;
        f(i,1,n){
            int x;
            cin>>x;
            if(l<=x&&x<=r)v.pb(x);
        }
        sort(all(v));
        int ans=0;
        for(auto it:v){
            if(k-it>=0){
                ans+=1;
                k-=it;
            }
            else break;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int v[200086];
LL n,tt;
int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tt;
    f(sb, 1, tt)
    {
        ull tim=0;
        cin >> n;
        vi c(n),ans(n);
        f(i, 0, n - 1)
        {
            cin >> v[i];
            c[i] =i;
        }
        sort(all(c),[](LL &a,LL & b){
            return v[a]>v[b];
        });
        f(i,1,n){
            ans[c[i-1]]=(i&1?(i+1)>>1:-(i>>1));
            tim+=2*abs(ans[c[i-1]])*v[c[i-1]];
        }
        cout<<tim<<"\n0 ";
        f(i,0,n-1){
            cout<<ans[i]<<(i==n-1?"\n":" ");
        }
    }
    return 0;
}
D1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
LL n,ans=0;
const int N=5e6+86;
int dp[N],cnt[N],m;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    vi v(n);
    int ans=0;
    f(i,1,n)cin>>v[i-1],m=max(v[i-1],m),cnt[v[i-1]]++;
    f(i,1,m){
        for(int j=i*2;j<=m;j+=i)cnt[i]+=cnt[j];
    }
    for(int i=m;i>0;i--){
        dp[i]=i*cnt[i];
        for(int j=2*i;j<=m;j+=i){
            dp[i]=max(dp[i],dp[j]+i*(cnt[i]-cnt[j]));
        }
        ans=max(dp[i],ans);
    }
    cout<<ans;
    return 0;
}

发表于 更新于 分类于 本文字数： 268 阅读时长 ≈ 1 分钟

主席树可A，回头试试其他做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
const int N=1e5+86;
int root[N],len[N],tot;
char c[N*30];
struct Node
{
    int l,r;
}tr[N*30];


void build(int &rt,int l,int r){
    rt=++tot;
    if(l==r){
        c[rt]='#';
        return ;
    }
    int mid=(l+r)>>1;
    build(tr[rt].l,l,mid);
    build(tr[rt].r,mid+1,r);
}

void update(int &rt,int last,int l,int r,int pos,char ch){
    rt=++tot;
    if(l==r){
        c[rt]=ch;
        return ;
    }
    tr[rt]=tr[last];
    int mid=(l+r)>>1;
    if(pos<=mid)update(tr[rt].l,tr[last].l,l,mid,pos,ch);
    else update(tr[rt].r,tr[last].r,mid+1,r,pos,ch);
}

char query(int rt,int l,int r,int pos){
    if (l == r)
        return c[rt];
    int mid = (l + r) >> 1;
    if (pos <= mid)
        return query(tr[rt].l, l, mid, pos);
    else
        return query(rt[tr].r, mid + 1, r, pos);
}

LL n,cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    build(root[0],1,n);
    f(i,1,n){
        char a;
        cin>>a;
        if(a=='T'){
            char ch;
            cin>>ch;
            cnt+=1;
            root[cnt]=root[cnt-1];
            len[cnt]=len[cnt-1]+1;
            update(root[cnt],root[cnt-1],1,n,len[cnt],ch);
        }
        else if(a=='U'){
            int d;
            cin>>d;
            cnt+=1;
            root[cnt]=root[cnt-d-1];
            len[cnt]=len[cnt-d-1];
        }
        else if(a=='Q'){
            int d;
            cin>>d;
            cout<<query(root[cnt],1,n,d)<<"\n";
        }
    }
    return 0;
}

0%