• 2022牛客暑期多校训练营4 个人题解

    title :2022牛客暑期多校训练营4 题解
    date : 2022-8-18
    tags : ACM,练习记录
    author : Linno

    2022牛客暑期多校训练营4 题解

    题目链接 ：https://ac.nowcoder.com/acm/contest/33189

    补题进度 ：9/14

    私信提醒我补题QAQ

    A - Task Computing

    排序不等式， ∑ i = 1 m w a i ∏ j i − 1 p a j \sum_{i=1}^m w_{a_i}\prod_j^{i-1}p_{a_j} ∑i=1m​wai​​∏ji−1​paj​​求最大收益。将 w [ i ] / ( 10000 − q [ i ] ) w[i]/(10000-q[i]) w[i]/(10000−q[i])大的结点排在前面。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
struct node{
	int w,q;
}s[N];

bool cmp(node A,node B){
	return A.w*(10000ll-B.q)>B.w*(10000ll-A.q);
}

int n,m;
double dp[25];

void Solve(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>s[i].w;
	for(int i=1;i<=n;++i) cin>>s[i].q;
	sort(s+1,s+1+n,cmp);
	for(int i=n;i>=1;i--){
		for(int j=m-1;j>=0;--j){
			dp[j+1]=max(dp[j+1],dp[j]*0.0001*s[i].q+s[i].w);
		}
	}
	printf("%.15lf",dp[m]);
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 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

    B - 2D Internet Angel

    C - Easy Counting Problem

    #include 
using namespace std;

const int N = 1<<18;
const int P = 998244353;

typedef vector<int> vi;

inline int add(int a, int b) { int r = a + b; return r < P ? r : r - P; }
inline int sub(int a, int b) { int r = a - b; return r < 0 ? r + P : r; }
inline int mul(int a, int b) { return 1ll * a * b % P; }
inline int qpm(int a, int b) {
    int r = 1;
    do if (b & 1) r = mul(r, a);
    while (a = mul(a, a), b >>= 1);
    return r;
}
inline int inv(int x) { return qpm(x, P - 2); }


namespace NTT1 {

using ::mul;
using ::inv;

const int W = 18, S = 1 << W, g = 3;
int w[S + 1], rev[S << 1], *r[W + 1];
void init() {
    for (int s = 0; s <= W&&(r[s]=rev+(1<<s),1); ++s)
        for (int i = 0; i != (1 << s); ++i)
            r[s][i] = (r[s][i >> 1] >> 1) | ((i & 1) << (s - 1));
    w[0] = 1; w[1] = qpm(g, (P - 1) / S);
    for (int i = 2; i <= S; ++i) w[i] = mul(w[i - 1], w[1]);
}

int m, s, im;
int init(int n) {
    for (s = 0, m = 1; m < n; m <<= 1, ++s);
    im = inv(m); return m;
}

void ntt(int* p, const int t) {
    for (int i = 0; i != m; ++i) if (i < r[s][i]) swap(p[i], p[r[s][i]]);
    for (int i = 1, z = 0; i != m; i <<= 1, z++)
        for (int j = 0; j != m; j += (i << 1))
            for (int k = 0, u, v; k != i; k++)
                u = p[j+k], v = mul(w[(t?(i<<1)-k:k)<<W-z-1], p[i+j+k]),
                p[j + k] = add(u, v), p[i + j + k] = sub(u, v);
    if (t) for (int i = 0; i != m; ++i) p[i] = mul(p[i], im);
}

int px[S], py[S];
vi pmul(const vi& p1, const vi& p2, int n = 0) {
    int n1 = p1.size(), n2 = p2.size(), n3 = n1 + n2 - 1;
    init(n3);
    copy_n(p1.begin(), n1, px); fill(px + n1, px + m, 0);
    copy_n(p2.begin(), n2, py); fill(py + n2, py + m, 0);
    ntt(px, 0); ntt(py, 0);
    for (int i = 0; i != m; ++i) px[i] = mul(px[i], py[i]);
    ntt(px, 1); vi p3(n3); copy_n(px, n3, p3.begin());
    if (n && n3 > n) p3.resize(n); return p3;
}

vi pinv(const vi& p1) {
    int n1 = p1.size(), n2 = (n1 + 1) >> 1;
    if (n1 == 1) return { inv(p1[0]) };
    else {
        vi p2 = pinv(vi(p1.begin(), p1.begin() + n2));
        init(n1 << 1);
        copy_n(p1.begin(), n1, px); fill(px + n1, px + m, 0);
        copy_n(p2.begin(), n2, py); fill(py + n2, py + m, 0);
        ntt(px, 0); ntt(py, 0);
        for (int i = 0; i != m; ++i)
            px[i] = mul(sub(2, mul(px[i], py[i])), py[i]);
        ntt(px, 1); vi p3(n1); copy_n(px, n1, p3.begin());
        return p3;
    }
}

}

using NTT1::init;
using NTT1::pmul;
using NTT1::pinv;

vi padd(const vi& p1, const vi& p2) {
    int n3 = max(p1.size(), p2.size());
    vi pr = p1; pr.resize(n3, 0);
    for (int i = 0; i != p2.size(); ++i) pr[i] = add(pr[i], p2[i]);
    return pr;
}

vi psub(const vi& p1, const vi& p2) {
    int n3 = max(p1.size(), p2.size());
    vi pr = p1; pr.resize(n3, 0);
    for (int i = 0; i != p2.size(); ++i) pr[i] = sub(pr[i], p2[i]);
    return pr;
}

const int M = 10000001;

int invs[M], fac[M], ifac[M];
int binom(int n, int k) { return mul(fac[n], mul(ifac[n - k], ifac[k])); }
void ginv() {
    invs[1] = 1; fac[0] = ifac[0] = 1;
    for (int i = 2; i != M; ++i) invs[i] = mul(invs[P % i], (P - P / i));
    for (int i = 1; i != M; ++i) fac[i] = mul(fac[i - 1], i);
    for (int i = 1; i != M; ++i) ifac[i] = mul(ifac[i - 1], invs[i]);
}

int main(void) {
    ginv();
    init();

    int w; scanf("%d", &w);
    vector<int> c(w);
    for (int& e : c) scanf("%d", &e);

    int s = 0;
    for (int e : c) s += e;

    vector<vi> g(1, vi(1, 1));
    for (int e : c) {
        vi f(ifac, ifac + e);
        
        vector<vi> tmp;
        tmp.push_back(vi(1, 0));
        for (int i = 0; i < (int)g.size(); ++i) {
            tmp[i] = psub(tmp[i], pmul(g[i], f));
            tmp.push_back(move(g[i]));
        }
        g = move(tmp);
    }

    int q; scanf("%d", &q);
    while (q--) {
        int n; scanf("%d", &n);
        int ans = 0;
        for (int i = 0; i <= w; ++i) {
            int u = min(n, (int)g[i].size() - 1);
            int z = qpm(i, n - u);
            for (int j = u; j >= 0; --j) {
                ans = add(ans, mul(mul(z, ifac[n - j]), g[i][j]));
                z = mul(z, i);
            }
        }
        printf("%d\n", mul(ans, fac[n]));
    }

    return 0;
}

    • 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
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151

    D - Jobs (Easy Version)

    随机种子要放在询问前面，不知道有多少人像我一样在这里wa了一发。开个三维数组直接记录最小值，然后做dp即可。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 405
//#define int long long
using namespace std;
const int N=405;
const int mod=998244353;
typedef long long ll;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(ll x){if(x>9) write(x/10);putchar(x%10+'0');}

ll n,q,m[15],sum[12][N][N],mi[12][N][N];
int seed;

inline ll fpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

inline ll solve(ll a,ll b,ll c){  //这里要O(n)查询 
	ll res=0;
	for(int i=1;i<=n;++i){
		if(mi[i][a][b]<=c) ++res;
	}
	return res;
}

void Solve(){
	cin>>n>>q;
	for(int i=0;i<=n;++i){
		for(int j=0;j<=400;++j){
			for(int k=0;k<=400;++k){
				sum[i][j][k]=mi[i][j][k]=inf;
			}
		}
	}
	for(int i=1;i<=n;++i){
		cin>>m[i];
		for(int j=1;j<=m[i];++j){
			ll a,b,c;
			cin>>a>>b>>c;
			sum[i][a][b]=min(sum[i][a][b],c);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=400;++j){
			for(int k=1;k<=400;++k){
				mi[i][j][k]=min(sum[i][j][k],min(mi[i][j-1][k],mi[i][j][k-1]));
			}
		}
	}
	cin>>seed;
	#include 
	mt19937 rng(seed);
	uniform_int_distribution<> u(1,400);
	int lastans=0;
	ll ans=0;
	for (int i=1;i<=q;i++){ //2e6
	    int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
	    int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
	    int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
	    lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend
//	    cout<
	    ans=(ans+lastans*fpow(seed,q-i)%mod)%mod;
	}
	cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 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
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    E - Jobs (Hard Version)

    #include 
//#define int long long
using namespace std;
const int N=405,mod=998244353;
typedef long long ll;

int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

inline ll fpow(ll a, ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

int sum[405][405][405],a[405][405];
int n, q;
set<pair<int,int>> s[1000005]; //某个公司最小b,c值的集合 

struct node{
	int x,y,id;
};
vector<node>e[405];

inline void add(int x1, int y1, int x2, int y2){  //对a做差分 
	++a[x1][y1];
	--a[x1][y2];
	--a[x2][y1];
	++a[x2][y2];
}

void insert(int i,int x,int y){ //将x和y插入i集合中 
	auto it=s[i].lower_bound({x,y});
	int last=x;
	auto tmp=it;
	int y1 = tmp == s[i].begin() ? 401 : (--tmp)->second;
	if (y1<=y) return; //存在更小的c则不需要插入 
	while(1){
		if (it==s[i].end()) break;
		add(last,y,it->first,y1);
		if (it->second<y) break;
		tmp = it++;
		last = tmp->first;
		y1 = tmp->second;
		s[i].erase(tmp);
	}
	s[i].insert({x, y}); 
}

signed main() {
	n=read();q=read();
	for(int i=1,m;i<=n;i++){
		s[i].insert({401,0});
		m=read();
		for(int j=1,a,b,c;j<=m;j++){
			a=read();b=read();c=read();
			e[a].push_back({b,c,i});
		}
	}
	for(int i=1;i<=400;++i){  //枚举每一个a 
		for(auto it:e[i]){
			insert(it.id,it.x,it.y); //将所有公司的b,c插入 
		}
		for(int x=1;x<=400;++x) {    //更新i的前缀和 
			for(int y=1;y<=400;++y){ 
				sum[i][x][y]=sum[i][x-1][y]+sum[i][x][y-1]-sum[i][x-1][y-1]+a[x][y];
			}
		}
	}

	int seed;
	seed=read();
	mt19937 rng(seed);
	uniform_int_distribution<> u(1, 400);
	int lastans=0;
	ll ans=0;
	for (int i=1; i<=q; i++) {
		int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
		int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
		int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
		lastans=sum[IQ][EQ][AQ];
		ans=(lastans+ans*seed%mod)%mod;
	}
	write(ans);putchar('\n');
	return 0;
}

    • 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
    • 86
    • 87
    • 88
    • 89
    • 90

    F - Palindromic Tree

    G - Wall Builder I

    H - Wall Builder II

    暴力枚举宽度，宽度一定时每一层尽量塞砖块进去肯定是最优的。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=105;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

struct node{
	int x1,y1,x2,y2;
}tmp[N*N];

int n,cnt[N],has[N];
vector<node>vt,ans;

void Solve(){
	cin>>n;
	int sum=0,C=inf;
	for(int i=1;i<=n;++i) cnt[i]=n-i+1,sum+=cnt[i]*i;  //每个砖的数量
	for(int p=n;p<=sum;++p){  //枚举宽 
		if(sum%p!=0||((sum/p)+p)>=C) continue;
		int hang=0,tmp=sum,flag=0;  //最开始有行数i
		for(int i=1;i<=n;++i) has[i]=cnt[i];
		vt.clear();
		while(tmp){
			int r=0;
			for(int k=n;k>=1;--k){
				while(r+k<=p&&has[k]){
					vt.emplace_back((node){r,hang,r+k,hang+1});
					--has[k];
					r+=k;
					tmp-=k;
				}
			}
			if(r==p) ++hang; 
			else{
				flag=1;
				break;
			}
		}
		if(flag) continue;  //不能组成一个矩形 
		C=(sum/p+p);
		swap(ans,vt);
	}
	cout<<2*C<<"\n";
	for(auto to:ans){
		cout<<to.x1<<" "<<to.y1<<" "<<to.x2<<" "<<to.y2<<"\n";
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 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

    I - Three Body

    J - Counting Fish Again

    K - NIO’s Sword

    最多7次我们就可以使1e6范围内的所有数都可达，并且每次变化的起点和终点都是固定的，枚举走x步从s出发可以到达的范围即可。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,ans=0,pw[15];

inline int calc(int s,int t){
	int res=0,L,R;
	while(1){
		++res;
		L=s,R=s+pw[res];
		if(L<=t&&t<R||L<=t+n&&t+n<R) break;
		s=s*10%n;
	}
	return res;
}

void Solve(){
	pw[0]=1;for(int i=1;i<=7;++i) pw[i]=pw[i-1]*10;
	cin>>n;
	if(n==1){
		cout<<"0\n";
		return;
	}
	for(int i=1;i<=n;++i){
		ans+=calc((i-1)*10%n,i%n);
	}
	cout<<ans<<"\n";
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 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

    L - Black Hole

    首先，合法的只有4面体、6面体、8面体、12面体和20面体。然后手玩或者geogebra一下得知每种形状变化后的对应关系。 4 − > 4 , 6 − > 8 , 8 − > 6 , 12 − > 20 , 20 − > 12 4->4,6->8,8->6,12->20,20->12 4−>4,6−>8,8−>6,12−>20,20−>12。然后抄一手公式求出边长就ok了。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
#define double long double
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
double a,mp[25],g=(1+sqrtl(5.0))/2.0;
int n,k,nxt[25];

void Solve(){
	cin>>n>>a>>k;
	if(n!=4&&n!=6&&n!=8&&n!=12&&n!=20){
		cout<<"impossible\n";
	}else{
		for(int i=1;i<=k;++i) a*=mp[n],n=nxt[n];
		printf("possible %d %.15Lf\n",n,a);
	}
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
    mp[4]=1.0/3;
    mp[6]=sqrtl(2.0)/2;
    mp[8]=sqrtl(2.0)/3;
    mp[12]=2.0*g/sqrtl(3.0-g)*g/sqrtl(10.0+2.0*sqrtl(5));
    mp[20]=(3.0+sqrtl(5.0))/(6.0*g);
    nxt[4]=4;nxt[6]=8;nxt[8]=6;nxt[12]=20;nxt[20]=12;
	int T=1;
	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 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

    M - Monotone Chain

    自己的板子套上了walkalone大佬的代码补的题……双指针太妙了。

    #include
#define Vector Point
//#define inf 0x7f7f7f7f
//#define int long long
//#define db long double
#define db long long
using namespace std;
typedef long long ll;
//const int N=1e5+7;
const db eps=1e-10,pi=acos(-1.0);
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

//inline int dcmp(db a){return a<-eps?-1:(a>eps?1:0);}  //处理精度 
//inline db Abs(db a){return a*dcmp(a);} //取绝对值 

struct Point{
    db x,y;
    Point(){ SetZero(); }
    Point(db _x,db _y){ Set(_x,_y); }
    inline void Set(db _x,db _y){ x=_x,y=_y; }
    inline void SetZero(){ x=y=0; }
    inline Point operator +(const Point &v) const{ return Point(x+v.x,y+v.y); }
    inline Point operator +=(const Point &v){ return *this=*this+v; }
    inline Point operator -() const{ return Point(-x,-y); }
    inline Point operator -(const Point &v) const{ return Point(x-v.x,y-v.y); }
    inline Point operator -=(const Point &v){ return *this=*this-v; }
    inline Point operator *(db f) const{ return Point(f*x,f*y); }
    inline friend Point operator *(db f,const Point &v){ return v*f; }
    inline Point operator *=(db f){ return *this=*this*f; }
    inline Point operator /(db f) const{ return *this*(1.0/f); }
    inline Point operator /=(db f){ return *this=*this/f; }
 
    inline bool operator <(const Point &b){
        auto up=[](const Point &a){
            if(a.IsZero()) return -1;
            return int(a.y>eps||(a.y>-eps&&a.x>-eps));
        };
        int qa=up(*this),qb=up(b);
        if(qa!=qb) return qa>qb;
        return Cross(*this,b)>eps;
    }
    inline bool IsZero() const{ return abs(x)<=eps&&abs(y)<=eps; }
    inline bool operator ==(const Point &v) const{ return (*this-v).IsZero(); }
    inline friend db Cross(const Point &p,const Point &q){ return p.x*q.y-p.y*q.x; }
    inline friend db Dot(const Point &p,const Point &q){ return p.x*q.x+p.y*q.y; }
    inline Point Rot90() const{ return Point(-y,x); }
    inline Point Rot90CW() const{ return Point(y,-x); }
    inline db SqrLen() const{ return x*x+y*y; }
    inline db Length() const{ return sqrt(x*x+y*y); }
    inline Point Normalized() const{
        db len=Length();
        if(len<=eps) return Point(0,0);
        db invLen=1.0/len;
        return Point(x*invLen,y*invLen);
    }
    inline Point Normalize(){ return *this=this->Normalized(); }
    inline db Arg() const{ return atan2(y,x); }
    inline friend istream &operator >>(istream &is,Point &v){ return is>>v.x>>v.y; }
    inline friend ostream &operator <<(ostream &os,const Point &v){
        os<<setiosflags(ios::fixed)<<setprecision(6);
        os<<"("<<setw(9)<<v.x<<','<<setw(9)<<v.y<<")";
        return os<<setprecision(6)<<resetiosflags(ios::fixed);
    }
};

struct Line{
    int u,v;
    Point ori,dir;
    Line(){ SetZero(); }
    Line(const Point &_ori,const Point &_dir){ Set(_ori,_dir); }
    inline void Set(const Point &_ori,const Point &_dir){
        ori=_ori,dir=_dir.Normalized();
    }
    inline void SetdbwoPoints(const Point &p1,const Point &p2){ Set(p1,p2-p1); }
    inline void SetZero(){ ori.SetZero(),dir.Set(1,0); }
    inline bool OnLeft(const Point &p){
        return Cross(dir,p-ori)>0;
    }
    inline db Arg() const{ return dir.Arg(); }
    inline friend Point Intersect(const Line &lA,const Line &lB){
        db k=Cross(lB.ori-lA.ori,lB.dir)/Cross(lA.dir,lB.dir);
        return lA.ori+lA.dir*k;
    }
};
 
bool argcmp(const Point &a,const Point &b){
	const auto quad=[](const Point &a){
		if(a.y<-eps) return 1;
		if(a.y>eps) return 4;
		if(a.x<-eps) return 5;
		if(a.x>eps) return 3;
		return 0; 
	};
	int qa=quad(a),qb=quad(b);
	if(qa!=qb) return qa<qb;
	const auto t=Cross(a,b);
	return t>eps; 
}

signed main(){
    int n=read();
    vector<Point>pt(n);
    for(int i=0;i<n;++i) scanf("%lld%lld",&pt[i].x,&pt[i].y);
    vector<Point>que;
    for(int i=1;i<n;++i){  //将向量加入队列 
		ll x=pt[i].x-pt[i-1].x,y=pt[i].y-pt[i-1].y;
		if(x||y){
			Point st=(Point){x,y};
			que.emplace_back(st);
		}
	}
	n=que.size();
	if(!n){  //一个点的情况 
		printf("YES\n 0 0 1 0");
		return 0;
	}
	sort(que.begin(),que.end(),argcmp);  //极角排序 
	for(int i=0;i<n;++i) que.emplace_back(que[i]);
	for(int l=0,r=0;l<n;++l){  //双指针，统计覆盖的射线数目 
		while(r<l+n&&(Cross(que[l],que[r]))>=0) ++r;
		if(r==l+n){
			printf("YES\n0 0 %lld %lld\n",-que[l].y,que[l].x);
			return 0;
		}
	}
	printf("NO");
}

    • 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
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127

    N - Particle Arts

    首先重构一下数组，把每一位上的1统计起来，然后尽量放，就得到了序列 x x x，即总和记为 s u m sum sum。

    σ 2 = 1 n ( x i − μ ) 2 \sigma^2=\frac{1}{n}(x_i-\mu)^2 σ2=n1​(xi​−μ)2代入 μ \mu μ再拆开平方项，两边同除 1 n 2 \frac{1}{n^2} n21​得： σ 2 n 3 = s u m i = 1 n ( x [ i ] ∗ n − s u m ) 2 \frac{\sigma^2}{n^3}=sum_{i=1}^n(x[i]*n-sum)^2 n3σ2​=sumi=1n​(x[i]∗n−sum)2，最后gcd约分一下结果，然后特判一下0就可以了。

    #include 
#define int __int128
using namespace std;
int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,sum,cnt,num,x,f[1000050],ans;
int gcd(int a,int b)
{
    if (a%b==0) return b;
    else return gcd(b,a%b);
}
signed main()
{
    n=read();
    for (int i=1;i<=n;++i)
    {
        x=read();
        sum+=x;
        cnt=0ll;
        while (x)
        {
            f[cnt++]+=(x&1);
            x>>=1;
        }
    }
    if (sum==0) { printf("0/1\n"); return 0; }
    for (int i=1;i<=n;++i)
    {
        num=0ll;
        for (int j=0;j<=20;++j)
            if (f[j]) {
                f[j]--;
                num|=(1<<j);
            }
        ans=ans+(num*n-sum)*(num*n-sum);
    }
    if (ans==0) { printf("0/1\n"); return 0;}
    int fenmu=n*n*n;
    int y=gcd(ans,fenmu);
    write(ans/y);
    putchar('/');
    write(fenmu/y);
    return 0;
}

    • 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
  • 相关阅读:
    查看MySQL的初始密码
    指定端口被system程序占用解决方法
    请协助我搭建 bert
    SOC验证环境的启动方式
    JVM 对象的访问方式
    多款可观测产品全面升级丨阿里云云原生 5 月产品月报
    电脑入门：路由器测试技术介绍及类型和方法
    pat_basic_1016 部分A+B
    降价背后，函数计算规格自主选配功能揭秘
    【洛谷 P1478】陶陶摘苹果（升级版）题解（多重集合+贪心算法）
  • 原文地址：https://blog.csdn.net/SC_Linno/article/details/126844690