2023湖南省赛

​​​​​​连接

目录

A:开开心心233

B:Square Game

C:室温超导

F:necklace

I:hard math

J:radius

K:tourist

---

补题中，会给出大部分代码

A:开开心心233

签到题 ，无论二分还是解方程还是直接for循环枚举都能直接通过啦

signed main()
{ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;
//	cout<<-3+sqrt(3*3+4*2*(n+m))<<'\n';int res1=n-(-3+sqrt(3*3+4*2*(n+m)))/2;int res2=n-(-3-sqrt(3*3+4*2*(n+m)))/2;if(res1<=n&&res1>=0) cout<<res1;else cout<<res2;
}

B:Square Game

#define f first
#define s second
const int N=1e6+5;
int f[N];
void init()
{for(int i=1;i<N;i++){int q=sqrt(i);map<int,bool>mp;if(q*q==i||q*q+1==i){for(int j=0;j<i;j+=q){mp[f[j]]=1;}int cnt=0;for(auto w:mp){if(w.f==cnt) cnt++;else break;}f[i]=cnt;}else{f[i]=f[i-1];}}
}
signed main() {ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);init();int n;cin>>n;int sum=0;for(int i=1;i<=n;i++){int x;cin>>x;sum^=f[x];}if(sum==0){cout<<"Second\n";}else{cout<<"First\n";}
}

C:室温超导

#define int long long
#define f first
#define s second
const int N = 500000 + 5;
char str[N];
struct Node
{int len, fa;int ch[26];
}node[N*4];
int tot = 1, last = 1;
int summ = 0;//不同的子串数
void extend(int c)
{int p = last, np = last = ++tot;node[np].len = node[p].len + 1;for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;if (!p) {node[np].fa = 1; summ += node[np].len - node[node[np].fa].len;}else{int q = node[p].ch[c];if (node[q].len == node[p].len + 1) { node[np].fa = q; summ += node[np].len - node[node[np].fa].len; }else {int nq = ++tot;summ -= node[q].len - node[node[q].fa].len;node[nq] = node[q], node[nq].len = node[p].len + 1;node[q].fa = node[np].fa = nq;summ += node[q].len - node[node[q].fa].len;summ += node[np].len - node[node[np].fa].len;summ += node[nq].len - node[node[nq].fa].len;for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;}}
}
signed main() {ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;cin >> str + 1;string t;cin >> t;t = ' ' + t;vector<int>sum(30);int all = 0;//int summ = 0;;for (int i = 1; i <= n - m + 1; i++) {int pre_tot = summ;extend(str[i] - 'a');//	summ = 0;//	for (int j = 2; j <= tot; j++) {//		summ += node[j].len - node[node[j].fa].len;//	}sum[str[i] - 'a'] += (summ - pre_tot);}all += summ;for (int i = n - m + 2; str[i]; i++) {int j = i - (n - m);int pre_tot = summ;extend(str[i] - 'a');//	summ = 0;//	for (int j = 2; j <= tot; j++) {//		summ += node[j].len - node[node[j].fa].len;//	}sum[str[i] - 'a'] += (summ - pre_tot);all += summ;all -= sum[t[j - 1] - 'a'];if (sum[t[j - 1] - 'a']) all++;}cout << all;
}

F:necklace

const int inf=0x3f3f3f3f;
int change[410][410];signed main()
{ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0);memset(change,0x3f,sizeof change);int n,m;cin>>n>>m;vector<int>s(n),t(n);for(int i=0;i<n;i++){cin>>s[i];}for(int i=0;i<n;i++){cin>>t[i];}while(m--){int a,b,c;cin>>a>>b>>c;change[a][b]=min(change[a][b],c);}for(int k=1;k<=400;k++){for(int i=1;i<=400;i++){for(int j=1;j<=400;j++){change[i][j]=min(change[i][j],change[i][k]+change[k][j]);}}}bool ok=0;int tot=inf;for(int i=0;i<n;i++){int sum=0;bool flag=1;for(int j=0;j<n;j++){if(s[j]==t[(i+j)%n]) continue;int p=inf;p=min(change[s[j]][t[(i+j)%n]],p);p=min(change[t[(i+j)%n]][s[j]],p);if(p>=inf){flag=0;break;				}sum+=p;}if(flag==0){
//			ok=0;
//			break;}else{ok=1;tot=min(tot,sum);}}if(!ok){cout<<-1<<'\n';}else{cout<<tot<<'\n';}
}

I:hard math

const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 1e9 + 7;
int a[N], b[N];
int dp[N][10][2][2];//上界，下界
int A;
int tot[N];
int dfs(int n, int sum, int up, int down)
{if (sum > A) return 0;if (dp[n][sum][up][down]) return dp[n][sum][up][down];if (n == 0) {if (sum == A) return 1; else {return 0;}}int l = 0, r = 9;if (up == 1) {r = b[n];}if (down == 1) {l = a[n];}int res = 0;for (int i = l; i <= r; i++) {if (tot[i]) {tot[i]++;res += dfs(n - 1, sum, up & (i == b[n]), down & (i == a[n]));res %= mod;tot[i]--;}else {tot[i]++;res += dfs(n - 1, sum + 1, up & (i == b[n]), down & (i == a[n]));res %= mod;tot[i]--;}}return dp[n][sum][up][down] = res;
}
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);int n;cin >> n;string s;cin >> s;reverse(s.begin(), s.end());s = ' ' + s;for (int i = 1; i <= n; i++) {a[i] = s[i] - '0';}cin >> s;reverse(s.begin(), s.end());s = ' ' + s;for (int i = 1; i <= n; i++) {b[i] = s[i] - '0';}cin >> A;cout << dfs(n, 0, 1, 1);
}

 

J:radius

不会写，借鉴一下链接

#define int long long
#define PII pair<int,int>
#define f first
#define s second
const int inf = 0x3f3f3f3f3f3f3f3f, N = 1e5 + 5, mod = 1e9 + 9;
int x[N], y[N], z[N];
int n;
struct node
{double pos;int val;
}a[2*N];
bool check(double r)
{int cnt = 0;for (int i = 1; i <= n; i++) {double res = r * r - y[i] * y[i] - z[i] * z[i];if (res < 0) continue;res = sqrt(res);a[++cnt] = { x[i] - res,1 };a[++cnt] = { x[i] + res,-1 };}sort(a + 1, a + 1 + cnt, [&](node i, node j) {return i.pos < j.pos;});int sum = 0;for (int i = 1; i <= cnt; i++) {sum += a[i].val;if (sum >= n / 2) {return 1;}}cnt = 0;for (int i = 1; i <= n; i++) {double res = r * r - y[i] * y[i] - x[i] * x[i];if (res < 0) continue;res = sqrt(res);a[++cnt] = { z[i] - res,1 };a[++cnt] = { z[i] + res,-1 };}sort(a + 1, a + 1 + cnt, [&](node i, node j) {return i.pos < j.pos;});sum = 0;for (int i = 1; i <= cnt; i++) {sum += a[i].val;if (sum >= n / 2) {return 1;}}cnt = 0;for (int i = 1; i <= n; i++) {double res = r * r - x[i] * x[i] - z[i] * z[i];if (res < 0) continue;res = sqrt(res);a[++cnt] = { y[i] - res,1 };a[++cnt] = { y[i] + res,-1 };}sort(a + 1, a + 1 + cnt, [&](node i, node j) {return i.pos < j.pos;});sum = 0;for (int i = 1; i <= cnt; i++) {sum += a[i].val;if (sum >= n / 2) {return 1;}}return 0;
}
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> x[i] >> y[i] >> z[i];}double l = 0, r = 1e6;for (int i = 0; i <= 50; i++) {double mid = (l + r) / 2;if (check(mid)) {r = mid;}else {l = mid;}}printf("%.10lf", l);
}

K:tourist

#define int long long
const int K=1<<7,mod=1e9+9;
int path[21][21];
int st[K];
int sz[10];
int siz(int x) {int cnt=0;while(x) {if(x&1) cnt++;x>>=1;}return cnt;
}
int a[21][21];
int f[21];
int n,m,k,d;
void mul(int f[],int a[21][21]) {int c[21]= {0};for(int j=1; j<=n; j++) {for(int k=1; k<=n; k++) {c[j]=(c[j]+f[k]*a[k][j])%mod;}}memcpy(f,c,sizeof c);
}
void mulself(int a[21][21]) {int c[21][21]= {0};for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {for(int k=1; k<=n; k++) {c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;}}}memcpy(a,c,sizeof c);
}
signed main() {ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m>>k>>d;d--;for(int i=0; i<k; i++) {int x;cin>>x;st[(1ll<<i)]=x;}while(m--) {int u,v;cin>>u>>v;path[u][v]=1;path[v][u]=1;}for(int i=0; i<(1ll<<k); i++) {int size=siz(i);memcpy(a,path,sizeof path);for(int j=0; j<k; j++) {if((i>>j)&1) {int p=st[(1ll<<j)];for(int k=1; k<=n; k++) {a[p][k]=0;a[k][p]=0;}}}for(int ii=1; ii<=n; ii++) {f[ii]=1;}int dd=d;for(; dd; dd>>=1) {if(dd&1) mul(f,a);mulself(a);}for(int j=1; j<=n; j++) {sz[size]+=f[j];sz[size]%=mod;}}int sum=0;for(int i=0; i<=k; i++) {if(i%2==0) {sum+=sz[i];sum%=mod;} else {sum=(sum-sz[i]+mod)%mod;}}cout<<sum<<'\n';
}