[补题]2019省赛训练赛
但我不想认输．．．．
调酒壶里的酸奶
这道题刚开始想歪了，一直在推公式？其实就是一个简单的记忆化搜索
最多100*100个状态 求最短路所以BFS
#include <bits/stdc++.h>
using namespace std;
int a,b,c;
struct node{
int x,y;
int step;
}st,en;
bool vis[105][105];
int bfs(){
queue<node>que;
st.x=0,st.y=0;
st.step=0;
que.push(st);
while(!que.empty()){
st=que.front();
que.pop();
if(st.x==c||st.y==c){
return st.step;
}
vis[st.x][st.y]=1;
if(!vis[0][st.y]){
en.x=0;
en.y=st.y;
en.step=st.step+1;
que.push(en);
}
if(!vis[st.x][0]){
en.x=st.x;
en.y=0;
en.step=st.step+1;
que.push(en);
}
if(st.x+st.y>=b){
en.x=st.x-(b-st.y);
en.y=b;
if(!vis[en.x][b]) {
en.step = st.step + 1;
que.push(en);
}
}else{
if(!vis[0][st.x+st.y]){
en.x=0;
en.y=st.x+st.y;
en.step = st.step + 1;
que.push(en);
}
}
if(st.x+st.y>=a){
en.y=st.y-(a-st.x);
en.x=a;
if(!vis[a][en.y]) {
en.step = st.step + 1;
que.push(en);
}
}else{
if(!vis[st.x+st.y][0]){
en.y=0;
en.x=st.x+st.y;
en.step = st.step + 1;
que.push(en);
}
}
if(!vis[a][st.y]){
en.x=a;
en.y=st.y;
en.step = st.step + 1;
que.push(en);
}
if(!vis[st.x][b]){
en.x=st.x;
en.y=b;
en.step = st.step + 1;
que.push(en);
}
}
return -1;
}
int main(){
while(scanf("%d%d%d",&a,&b,&c)!=EOF){
memset(vis,0,sizeof(vis));
int ans=bfs();
if(ans==-1){
puts("impossible");
}else{
printf("%d\n",ans);
}
}
return 0;
}
fps游戏
高中数学题类型的?通过边的关系求出弧度制的角，然后*180 这题可能卡精度 除法可能有问题 所以需要一个个加
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
int main() {
int d, r, c;
double a;
scanf("%d%d%d%lf", &d, &r, &c, &a);
double tmp = atan(1.0 * r / d);
tmp = tmp / pi * 180;
int k=0;
double t=0;
while(k<=c&&t<=tmp){
t+=a;
k++;
}
printf("%d",max(0,c-k));
return 0;
}
小C的数学问题
区间价值为区间和乘上区间内的最小值
用单调栈 每个点对答案的贡献
右边是到第一个比其小的数的前一个
维护一个单调栈 当栈顶大于这个数 就把栈顶弹出 同时将弹出的块右边修正 而新加入的数就将左边更新
然后前缀和搞一搞就可以了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 7;
struct node {
ll v;
int st, ed;
} s[maxn];
int q[maxn];
ll sum[maxn];
template<class T>
void read(T &res) {
res = 0;
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
int main() {
int n;
read(n);
for (register int i = 1; i <= n; ++i) {
read(s[i].v);
s[i].st = s[i].ed = i;
sum[i] = sum[i - 1] + s[i].v;
}
int tail = 0;
for (int i = 1; i <= n; ++i) {
if (tail == 0) {
q[tail++] = i;
} else {
if (s[i].v >= s[q[tail - 1]].v) {
q[tail++] = i;
} else {
while (tail != 0 && s[i].v < s[q[tail - 1]].v) {
s[i].st = s[q[tail - 1]].st;
s[q[tail - 1]].ed = i - 1;
tail--;
}
q[tail++] = i;
}
}
}
while (tail != 0) {
s[q[tail - 1]].ed = n;
tail--;
}
int l = 0, r = 0;
ll maxx = -1;
for (register int i = n; i >= 1; --i) {
if ((sum[s[i].ed] - sum[s[i].st - 1]) * s[i].v > maxx) {
maxx = (sum[s[i].ed] - sum[s[i].st - 1]) * s[i].v;
l = s[i].st, r = s[i].ed;
}
}
printf("%lld\n", maxx);
printf("%d %d\n", l, r);
return 0;
}
Master of Phi
数学问题 公式好好写应该能做出来
最后就是求一个：
\[\sum_{d|n}n*\prod_{p|n}(1-1/p) \]
其中d就是n的因子 而p是n的质因子
原文中给出了质因子和质因子的个数
若\(2^2 3^2\)
\[ans=(1-1/2)(1-1/3)*4 \]
最后全部加起来乘以n
dfs 组合型枚举
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 30;
const int mod = 998244353;
ll qpow(ll k,int n){
ll res=1;
while(n){
if(n&1) res=res*k%mod;
k=k*k%mod;
n>>=1;
}
return res;
}
ll q[maxn];
ll p[maxn],ans,inv[maxn];
int m;
template<class T>
void read(T &res) {
res = 0;
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
void dfs(int cnt,ll num){
if(cnt==m+1){
ans=(ans+num)%mod;
return;
}
dfs(cnt+1,num);
dfs(cnt+1,(p[cnt]-1)*num%mod*q[cnt]%mod*inv[cnt]%mod);
}
int main() {
int T,n;read(T);
while(T--){
read(m);
n=1;
ans=0;
for(int i=1;i<=m;++i){
read(p[i]);
read(q[i]);
inv[i]=qpow(p[i]%mod,mod-2);
n=n*qpow(p[i],q[i])%mod;
}
dfs(1,1);
printf("%lld\n",ans*n%mod);
}
return 0;
}
这个也有纯数学的方法
题目是求狄利克雷函数 而且是积性函数 所以他们的狄利克雷卷积也是积性函数
具体思想是推出每个\(p^q\)的狄利克雷卷积的式子 带进去然后乘起来
\[设n=p^q \]
\[\sum_{d|n}\phi(d)\frac{n}{d}=\phi(1)*p^q+\sum_{i=1}^q\phi(p^i)\frac{p^q}{p^i} \]
\[=p^q+p^q(1-\frac{1}{p})\sum_{i=1}^q1 \]
\[=p^q+p^{q-1}q(p-1) \]
\[=p^{q-1}(p+pq-q) \]
Cosmetic Survey
题意几个概念弄懂其实不是很难：
最后主要问题转化为：
1.路径上最短的边是这个路径的权值
2.\(s[u][v]\)的值是u到v所有路径权值的最大值
然后SPFA的松弛操作为：
\[d[s][v]=max(min(d[s][v],val),d[s][v]) \]
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505,M=505*505;
int he[N],ver[M],edge[M],nex[M],s[N];
int n,m,tot;
queue<int> q;
bool vis[N];
int a[N];
int d[N][N];
int ent[N][N];
vector<int> ant;
void add(int u,int v,int w)
{
ver[++tot]=v;
edge[tot]=w;
nex[tot]=he[u];
he[u] = tot;
}
void spfa(int st)
{
memset(s,0,sizeof s);
memset(vis,0,sizeof vis);
s[st]=0;
vis[st]=1;
q.push(st);
s[st]=0x3f3f3f3f;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=he[x];i;i=nex[i]){
int y=ver[i];
int z=edge[i];
if(s[y]<min(s[x],z)){
s[y]=min(s[x],z);
if(!vis[y]){
q.push(y);
vis[y]=1;
}
}
}
}
}
int main()
{
scanf("%d %d",&n,&m);
while(m--){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==0)
a[i]=1e9;
}
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i]<a[j])
d[i][j]++;
else if(a[i]>a[j])
d[j][i]++;
}
}
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(j!=i){
if(d[i][j]>d[j][i])
{
add(i,j,d[i][j]);
}
else if(d[j][i]>d[i][j])
{
add(j,i,d[j][i]);
}
}
}
}
for(int i=1;i<=n;i++)
{
spfa(i);
for(int j=1;j<=n;j++)
{
if(j!=i)
ent[i][j]=s[j];//cout<<s[j]<<endl;
}
}
for(int i=1;i<=n;i++)
{
int f=0;
for(int j=1;j<=n;j++)
{
if(i!=j)
{
if(ent[i][j]<ent[j][i])
{
f=1;
break;
}
}
}
if(!f)
{
ant.push_back(i);
}
}
for(int i=0;i<ant.size();i++)
{
if(i)
printf(" ");
printf("%d",ant[i]);
}
printf("\n");
return 0;
}
T-net
挺绕的一个贪心
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int s[N];
int d[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, a, b;
ll ans = 0;
cin >> n >> a >> b;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
sort(s + 1, s + 1 + n);
if (a > b) swap(a, b);
s[0] = s[1], s[n + 1] = s[n];
for (int i = 1; i <= n; ++i) {
if (d[i] == a) continue;
if (d[i] != b) {
if (s[i] - s[i - 1] <= a && s[i + 1] - s[i] <= a) {
d[i] = a;
continue;
}
if (s[i] - s[i - 1] > b || s[i + 1] - s[i] > b) {
cout << -1 << endl;
return 0;
}
}
d[i] = b;
int j = i;
while (s[i] + b >= s[j] && j <= n) ++j;
--j;
//判断 d[j]需不需要用b
bool flag = 0;
for (int k = i + 1; k < j; ++k) {
if (s[k] - s[k - 1] > a || s[k + 1] - s[k] > a) {
flag = 1;
break;
}
}
if (!flag) continue;
else d[j] = b;
for (int r = j - 1; r > i; --r) {// 将右边相差a但左边相差b的变成a
if (d[r]) break;
if (s[r + 1] - s[r] <= a) {
d[r] = a;
} else break;
}
for (int l = i + 1; l < j; ++l) {// 将左边相差a但右边相差b的变成a
if (d[l]) break;
if (s[l] - s[l - 1] <= a) {
d[l] = a;
} else break;
}
}
for (int i = 1; i <= n; ++i) {
ans += d[i];
}
cout << ans << endl;
return 0;
}
/* 原先写法 虽然相邻的会优但没有处理左边a右边b或者右边a左边b的情况
* if(a[i]-a[i-1]<=x&&a[i+1]-a[i]<=x)
ans+=x;
else if(a[i]-a[i-1]<=y&&a[i+1]-a[i]<=y)
ans+=y;
*/
LED
二分误差 然后check
check时只要尽量满足就行
v的只用就是排序
先是第一部分 当l大于误差的时候break
这个时候是L1灯的第一个
维护一个最大和最小的区间 每次更新
当前的灯的最大值小于之前的最小值 直接返回false
当前的灯的最小值大于之前的最大值那么就是到L2区间了 后面同理
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5 + 7;
struct node {
int v;
double l;
} s[maxn];
int n;
bool check(double p) {
int i;
for (i = 1; i <= n; ++i) {
if (s[i].l > p) {
break;
}
}
if (i > n) return true;
double minn = s[i].l - p, maxx = s[i].l + p;
++i;
for (; i <= n; ++i) {
if (s[i].l + p < minn) {
return false;
}
if (s[i].l - p <= maxx) {
minn = max(s[i].l - p, minn);
maxx = min(s[i].l + p, maxx);
} else if (s[i].l - p > maxx) {
break;
}
}
if (i > n)return true;
minn = s[i].l - p, maxx = s[i].l + p;
for (; i <= n; ++i) {
if (s[i].l + p < minn) {
return false;
}
if (s[i].l - p <= maxx) {
minn = max(s[i].l - p, minn);
maxx = min(s[i].l + p, maxx);
} else if (s[i].l - p > maxx) {
return false;
}
}
return true;
}
bool cmp(node a, node b) {
return a.v < b.v;
}
int main() {
scanf("%d", &n);
double ans = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d%lf", &s[i].v, &s[i].l);
if (s[i].v == 0) ans = max(ans, s[i].l);
}
sort(s + 1, s + 1 + n, cmp);
double l = 0, r = 1e15;
while (l + 1e-5 < r) {
double mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else l = mid;
}
printf("%.1f\n", max(l, ans));
return 0;
}
京公网安备 11010502036488号