Starry

发表于 更新于 分类于 本文字数： 205 阅读时长 ≈ 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
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll n,a[(int)1e5+9],b[(int)1e5+9];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;++i)cin>>x,a[x]=i;
    for(int i=1,x;i<=n;++i)cin>>x,b[i]=a[x];
    vi v(1,-1);
	for(int i=1;i<=n;++i){
		if(b[i]>v.back())v.push_back(b[i]);
		else *upper_bound(all(v),b[i])=b[i];
	}
	cout<<v.size()-1;
    return 0;
}

发表于 更新于 分类于 本文字数： 389 阅读时长 ≈ 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
#include<bits/stdc++.h>

using namespace std;

using ll=long long;


const int maxn=1e5+9;
struct Node{
	ll l,r,v,ma;
}tr[maxn<<2];

ll n,m,a[maxn];

void build (int l,int r,int tot){
	if(l==r){
		tr[tot].v=tr[tot].ma=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,tot<<1),build(mid+1,r,(tot<<1)|1);
	tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v,tr[tot].ma=max(tr[tot<<1].ma,tr[(tot<<1)|1].ma);
}

void modify(int x,int l,int r,int tot){
	if(l==r){
		tr[tot].v=tr[tot].ma=a[l];
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)modify(x,l,mid,tot<<1);
	else modify(x,mid+1,r,(tot<<1)|1);
	tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v,tr[tot].ma=max(tr[tot<<1].ma,tr[(tot<<1)|1].ma);
}

void getmod(int nl,int nr,int tot,int l,int r,int mod){
	if(nl==nr){
		tr[tot].v=tr[tot].ma=a[nl]=a[nl]%mod;
		return;
	}
	if(tr[tot].ma<mod)return;
	int mid=(nl+nr)>>1;
	if(mid>=l)getmod(nl,mid,tot<<1,l,r,mod);
	if(mid<r)getmod(mid+1,nr,(tot<<1)|1,l,r,mod);
	tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v,tr[tot].ma=max(tr[tot<<1].ma,tr[(tot<<1)|1].ma);
}

ll getsum(int nl,int nr,int tot,int l,int r){
	if(nl>=l&&nr<=r)return tr[tot].v;
	ll mid=(nl+nr)>>1,res=0;
	if(mid>=l)res+=getsum(nl,mid,tot<<1,l,r);
	if(mid<r)res+=getsum(mid+1,nr,(tot<<1)|1,l,r);
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>a[i];
		build(1,n,1);
	for(int i=1,x,y,z,w;i<=m;++i){
		cin>>x>>y>>z;
		if(x==1){
			cout<<getsum(1,n,1,y,z)<<"\n";
		}else if(x==2){
			cin>>w;
			getmod(1,n,1,y,z,w);
		}else {
			a[y]=z;
			modify(y,1,n,1);
		}
	}
}

发表于 更新于 分类于 本文字数： 282 阅读时长 ≈ 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
#include<bits/stdc++.h>

using namespace std;

using ll =long long ;

const int maxn=5e5+9;

struct Node{
	int l,r,v;
}tr[maxn<<2];

int gcd(int ma,int mi){return mi?gcd(mi,ma%mi):ma;}

int a[maxn],n,m,cnt;

void build(int l,int r,int now){
	if(l==r){
		tr[now].v=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,now<<1),build(mid+1,r,(now<<1)|1);
	tr[now].v=gcd(tr[now<<1].v,tr[(now<<1)|1].v);
}

void modify(int x,int l,int r,int now){
	if(l==r){
		tr[now].v=a[x];
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)modify(x,l,mid,now<<1);
	else modify(x,mid+1,r,(now<<1)|1);
	tr[now].v=gcd(tr[now<<1].v,tr[(now<<1)|1].v);
}

void check(int l,int r,int now,int ll,int rr,int x){
	if(cnt>=2)return;
	if(l==r){
		if(tr[now].v%x)cnt+=1;
		return ;
	}
	if(tr[now].v%x==0)return ;
	int mid=(l+r)>>1;
	if(mid>=ll)check(l,mid,now<<1,ll,rr,x);
	if(mid<rr)check(mid+1,r,(now<<1)|1,ll,rr,x);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	build(1,n,1);
	cin>>m;
	for(int i=1,x,y,z,w;i<=m;++i){
		cin>>x>>y>>z;
		if(x&1){
			cnt=0;
			cin>>w;
			check(1,n,1,y,z,w);
			cout<<(cnt>=2?"NO\n":"YES\n");
		}else{
			a[y]=z;
			modify(y,1,n,1);
		}
	}
}

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

有思路但老是被否，自己却难以implement

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
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}

ll n,a[109];
__int128 cf[109],s[109],cfs[109],dp[109][109]; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<n;++i)cf[i]=a[i+1]-a[i];
    for(int i=1;i<n;++i)s[i]=s[i-1]+cf[i],cfs[i]=cfs[i-1]+cf[i]*cf[i];
    for(int i=1;i<n;++i){
        for(int j=1;j<=i;++j){
            for(int k=0;i-k>=j;++k){
                dp[i][j]=max(dp[i][j],dp[i-k-1][j-1]+(s[i]-s[i-k-1])*(s[i]-s[i-k-1]));
            }
        }
    }
    for(int i=1;i<=n;++i){
        write(dp[n-1][max(n-1-2*i,1ll)]),putchar('\n');;
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 216 阅读时长 ≈ 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
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll l,n,dis; 
vector <pair<double,double>> v;

 bool ck(double x,double y){
 	for(auto [aa,bb]:v){
 		if(n*n*((aa-x)*(aa-x)+(bb-y)*(bb-y))<=(l*1.0)*(l*1.0))return false;
 	}
 	return true;
 }

int main()
{
    scanf("%lld%lld",&n,&l);
    std::random_device rd;
    std::default_random_engine eng(rd());
    std::uniform_real_distribution<double> num(0.0,l*1.0);
    for(int i=1;i<=n;++i){
    	double x,y;
    	scanf("%lf%lf",&x,&y);
    	v.push_back({x,y});
    }
    for(int i=1;i<=1e4;++i){
    	double x=num(eng),y=num(eng);
    	if(ck(x,y)){
    		printf("%.8lf %.8lf",x,y);
    		return 0;
    	}
    }
    printf("%s","GG\n");
    return 0;
}
0%