T1
水题。
# include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,k;
double gpt[N],a[N],b[N];
void FIO(void)
{
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
return;
}
int main(void)
{
FIO();
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; i++)
{
cin >> gpt[i] >> a[i];
b[i] = gpt[i] / a[i];
}
sort(b + 1,b + n + 1);
printf("%.2lf
",b[n - k + 1]);
return 0;
}
T2
前缀和,单次询问(mathcal{O}(1)),预处理(mathcal{O}(n))。
# include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100005;
long long a[N],q[N];
void FIO(void)
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
return;
}
int main(void)
{
FIO();
int m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
{
scanf("%lld",&a[i]);
}
for(int i = 1; i <= n; i++) q[i] = q[i - 1] + a[i];
int l,r;
while(m--)
{
scanf("%d%d",&l,&r);
printf("%lld
",q[r] - q[l - 1]);
}
return 0;
}
T3
递推(或者叫DP),设(f_{i,j,k})指走到((i,j)),积分为(k)的线路条数。
[f_{i,j,k} =
egin{cases}
1 & i = j = 1,k = a_{1,1}\
f_{i - 1,j,k - a_{i,j}} + f_{i,j - 1,k - a_{i,j}} & exttt{otherwise}
end{cases}
]
你以为是(mathcal{O}(n^2m^2))?并不是,对于((i,j)),其最大(k)为(10(i + j - 1)),易得。
# include <bits/stdc++.h>
using namespace std;
const int N = 102;
int n,m,a[N][N];
int p;
int dp[N][N][2 * N * 10];
const int mod = 1e9 + 7;
int DP(void)
{
dp[1][1][a[1][1]] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(i == 1 && j == 1) continue;
for(int k = a[i][j]; k <= (i + j - 1) * 10; k++)
{
dp[i][j][k] = (dp[i - 1][j][k - a[i][j]] + dp[i][j - 1][k - a[i][j]]) % mod;
// printf("dp[%d][%d][%d] = %d
",i,j,k,dp[i][j][k]);
}
}
}
return dp[n][m][p] % mod;
}
void FIO(void)
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
return;
}
int main(void)
{
FIO();
scanf("%d%d%d",&n,&m,&p);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%d",&a[i][j]);
}
}
printf("%d
",DP());
return 0;
}
T4
吐槽题面,一开始看错一堆
注意事项:
- 最后题目中描述的“如果一头奶牛以能量(R)着陆在了位置(x)”这里的(x)不一定是(x_i)上的点,是任意一个位置。
- 干草包爆炸不连续,题目中有点含糊不清,导致我(10)分。
看到题很显然想到二分(R)。考虑对于(R)已知,如何去判断其是否合法。
如果我们想让一个炸弹炸掉(x_i,x_j)的干草包((x_i < x_j)),显然放在中间(即(frac{x_i + x_j}{2}))为最优,那么易得如果(x_j - x_i le 2R),那么就能炸掉(x_i,x_j)和他们中间的所有干草包。
于是,题目变成了用前后差(le 2R)的区间最小覆盖(?怎么感觉说起来怪怪的
# include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int k;
int n;
long long x[N],c[N];
long long M = 0;
bool check(long long R)
{
int i = 1,cnt = 0;
while(i <= n)
{
int now = i + 1;
while(now <= n && x[now] - x[i] <= 2 * R) now++;
// if(R == 4) printf("now = %d
",now);
cnt++;
if(cnt > k) return 0;
if(now > n) break;
i = now;
// if(R == 4) printf("i = %d
",i);
}
return cnt <= k;
}
long long qfind(void)
{
long long l = 0,r = M;
long long ans = 0;
while(l <= r)
{
int mid = (l + r) >> 1;
if(check(mid))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
void FIO(void)
{
freopen("angry.in","r",stdin);
freopen("angry.out","w",stdout);
return;
}
int main(void)
{
FIO();
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; i++)
{
scanf("%lld",&x[i]);
}
sort(x + 1, x + n + 1);
M = x[n] << 1;
printf("%lld
",qfind());
return 0;
}