信息学蒟蒻域ACM模拟赛题解
程序员文章站
2022-03-09 16:09:44
...
因为x很大，我们可以考虑取对数（很好想的），然后就是比较x*log10(x)和log10(n!)之间的大小了。
其中后者我们可以利用斯特林公式（注意精度问题）：
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 286000
#define PI 3.1415926
#define lowbit(x) (x&-x)
#define eps 1e-9
int main(void)
{
double x, y=0,ans=0;
ll i;
scanf("%lf", &x);
if (x == 1)
{
printf("2\n");
return 0;
}
x = x*log10(x)+1;
double l = 0,r= 17777777778;
while (r - l >= 0.000001)
{
double mid = (l + r) / 2.0;
y = (double)(log10(2 * PI*mid) / 2 + mid*log10(mid / 2.718281828459));
if (y - x >= eps)
{
ans = mid;
r = mid;
}
else
l = mid;
}
printf("%.0f\n", ans);
}这道题和BZOJ windy数一样，简单的数位DP搞搞就OK了。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 560050
#define lowbit(x) (x&-x)
#define eps 1e-9
#define maxn 2000005
ll dp[30][15], len1, a, b, t[100];
ll work(ll x)
{
int res = 0;
while (x)
t[++res] = x % 10, x /= 10;
return res;
}
ll dfs(ll len, ll pos, ll flag, ll id)
{
ll ans, num, i, j;
if (len == 0)
return 1;
if (flag == 0 && dp[len][pos] != -1)
return dp[len][pos];
else
ans = 0;
if (flag)
num = t[len];
else
num = 9;
for (i = 0;i <= num;i++)
{
if (pos == -1 || abs(i - pos) >= 2)
{
if (i == 0 && id)
ans += dfs(len - 1, -1, flag && i == num, i == 0 && id);
else
ans += dfs(len - 1, i, flag && i == num, i == 0 && id);
}
}
if (flag == 0 && id == 0)
dp[len][pos] = ans;
return ans;
}
int main(void)
{
ll a, b, i, j, ans1 = 0, ans2 = 0;
memset(dp, -1, sizeof(dp));
scanf("%lld%lld", &a, &b);
len1 = work(a - 1);
ans1 = dfs(len1, -1, 1, 1);
len1 = work(b);
ans2 = dfs(len1, -1, 1, 1);
printf("%lld\n", ans2 - ans1);
return 0;
}题解：一开始用的递推瞎搞搞，然后怎么测怎么对，陷入了无尽的绝望了，浪费了很长时间后，换了一种姿势，用了背包写了一发，直接AC，感觉又是玄学，但是没办法，背包的话很简单，定义dp[i][j]：表示当前选的集合里权值和为i且已经放了j个士兵的状态是否合法（合法为1，不合法为0），然后按照一般的背包递推就OK了。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 5600
#define lowbit(x) (x&-x)
#define eps 1e-9
int dp[8205][205], a[205];
int main(void)
{
int n, i, j, k, sum = 0, h;
scanf("%d", &n);
for (i = 1;i <= n;i++)
{
scanf("%d", &a[i]);
sum += a[i];
}
dp[0][0] = 1;
for (i = 1;i <= n;i++)
for (j = 8000;j >= a[i];j--)
{
for (k = 1;k <= i;k++)
{
if (dp[j - a[i]][k - 1] == 0)
continue;
dp[j][k] = 1;
}
}
int x=0, y;
for (i = sum/2;i >= 0;i--)
if (dp[i][n / 2] || dp[i][n / 2 + (n % 2 != 0)])
{
x = i;
break;
}
y = sum - x;
if (x > y) swap(x, y);
if (n == 1)
printf("0 %d\n", sum);
else
printf("%d %d\n", x, y);
return 0;
}简单的kmp应用，当第一次匹配完成时直接break就好啦。。。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 560050
#define lowbit(x) (x&-x)
#define eps 1e-9
char s1[maxn], s2[maxn];
ll p[maxn], q[maxn], ans;
void print()
{
int i, j = 0;
p[1] = 0;
int len = strlen(s1 + 1);
for (i = 2;i <= len;i++)
{
while (j>0 && s1[j + 1] != s1[i])
j = p[j];
if (s1[i] == s1[j + 1])
j++;
p[i] = j;
}
}
void kmp()
{
int i, j = 0, sum = strlen(s1 + 1);
int len = strlen(s2 + 1);
for (i = 1;i <= len;i++)
{
while (j>0 && s2[i] != s1[j + 1])
j = p[j];
if (s1[j + 1] == s2[i])
j++;
if (j == sum)
{
ans = i;
j = p[j];
break;
}
}
}
int main(void)
{
int T, i, j;
scanf("%d", &T);
while (T--)
{
scanf("%s", s2+1);
scanf("%s", s1+1);
print();kmp();
printf("%lld\n", ans-strlen(s1+1)+1);
}
return 0;
}这道题算是A的最快的一道了，最优决策一定是唯一固定的，故我的一个做法是令右括号为‘-1’，左括号为‘1’，然后记录最大值，答案肯定是（最大值+1）/2,其实本质上就是当前括号左边有几个括号没有完成配对。。。。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 286000
#define lowbit(x) (x&-x)
#define eps 1e-9
int main(void)
{
char c;
int i, sum = 0, mx = 0, n;
scanf("%d", &n);
for (i = 1;i<=n;i++)
{
scanf(" %c", &c);
if (c == '(')
sum -= 1;
else
sum += 1;
mx = max(mx,abs(sum));
}
printf("%d\n", mx / 2 + (mx % 2 != 0));
return 0;
}赛后补的一道题，单调栈用两次，一次求所有子序列的最小值，一次求最大值，然后相减即可。。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 386000
#define PI 3.1415926
#define lowbit(x) (x&-x)
#define eps 1e-9
struct node
{
ll x, l, r, y;
}a[maxn];
stack<node>t;
int main(void)
{
ll ans1 = 0, ans2 = 0;
int n, i, j;
scanf("%d", &n);
for (i = 1;i <= n;i++)
scanf("%lld", &a[i].x), a[i].y = i;
for (i = 1; i <= n;i++)
{
a[i].l = i;
while (t.empty() == 0 && t.top().x >= a[i].x)
{
a[t.top().y].r = i - 1;
a[i].l = a[t.top().y].l;
t.pop();
}
t.push(a[i]);
}
while (t.empty() == 0)
{
a[t.top().y].r = n;
t.pop();
}
for (i = 1;i <= n;i++)
{
ans2 += a[i].x*(i - a[i].l + 1)*(a[i].r - i + 1);
a[i].l = a[i].r = i;
}
for (i = 1; i <= n;i++)
{
a[i].l = i;
while (t.empty() == 0 && t.top().x <= a[i].x)
{
a[t.top().y].r = i - 1;
a[i].l = a[t.top().y].l;
t.pop();
}
t.push(a[i]);
}
while (t.empty() == 0)
{
a[t.top().y].r = n;
t.pop();
}
for (i = 1;i <= n;i++)
ans1 += a[i].x*(i - a[i].l + 1)*(a[i].r - i + 1);
printf("%lld\n", ans1 - ans2);
return 0;
}这是一道经典题了，大二的时候做过，结论是C(2*n,n)-C(2*n,n-1);（注意要用逆元）
具体证明可以自行百度。。。。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 5600500
#define lowbit(x) (x&-x)
#define eps 1e-9
ll fac[maxn], inv[maxn];
ll Pow(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = (ans*a) % mod;
a = (a*a) % mod;
b >>= 1;
}
return ans;
}
int main(void)
{
ll n, a, b;
fac[0] = inv[0] = 1;
for (int i = 1;i <= 2000005;i++)
{
fac[i] = (fac[i - 1] * i) % mod;
inv[i] = Pow(fac[i], mod - 2);
}
scanf("%lld", &n);n = n - 1;
ll ans1 = fac[2 * n] * inv[n] % mod*inv[n] % mod;
ll ans2 = fac[2 * n] * inv[n + 1] % mod*inv[n - 1] % mod;
printf("%lld\n", (ans1-ans2+mod)%mod);
return 0;
}字典树模板题，手码+AC=5分钟。。。写的最快的一道字典树题，唯一的处理就是当前字符标记一下有多少字符串的前缀经过。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 286000
#define lowbit(x) (x&-x)
#define eps 1e-9
int siz, a[maxn][30],cnt[maxn][30];
char s1[55], s2[55];
void insert()
{
int i, j, now = 0,len=strlen(s2);
for (i = 0;i < len;i++)
{
int v = s2[i] - 'a';
if (a[now][v] == 0)
a[now][v] = ++siz;
cnt[now][v]++;
now = a[now][v];
}
}
double query()
{
double res = 0.0;
int i, j, now = 0;
int len = strlen(s2);
for (i = 0;i < len;i++)
{
int v = s2[i]-'a';
if (a[now][v] == 0)
break;
res += (double)(i+1)/(double)len*(double)cnt[now][v];
now = a[now][v];
}
return res;
}
int main(void)
{
int n,i,q;
scanf("%d", &n);
scanf("%s", s1);
for (i = 1;i <= n;i++)
{
scanf("%s", s2);
insert();
}
strcpy(s2, s1);
printf("%.2f\n", query());
scanf("%d", &q);
while (q--)
{
scanf("%s", s2);
printf("%.2f\n", query());
}
return 0;
}比赛签到题，我是拿递归写的。。。。
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 560050
#define lowbit(x) (x&-x)
#define eps 1e-9
ll work(ll x)
{
if (x <= 1)
return 0;
return work(x / 2 + (x % 2 != 0)) + 1;
}
int main(void)
{
ll n;
scanf("%lld", &n);
printf("%lld\n", work(n));
return 0;
}同样是水题，我们可以先计算出每条线的斜率，然后每次O(n)查找即可
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 5600
#define lowbit(x) (x&-x)
#define eps 1e-9
struct node
{
double x, y, xx, yy,flag;
}a[maxn],b;
int main(void)
{
int n, i, j, q;
while (scanf("%lld", &n) != EOF)
{
for (i = 1;i <= n;i++)
{
scanf("%lf%lf%lf%lf", &a[i].x, &a[i].y, &a[i].xx, &a[i].yy);
double t1, t2;
if (a[i].x > a[i].xx)
t1 = a[i].xx, t2 = a[i].yy, a[i].xx = a[i].x, a[i].yy = a[i].y, a[i].x = t1, a[i].y = t2;
a[i].flag = (a[i].yy - a[i].y) / (a[i].xx - a[i].x);
}
scanf("%d", &q);
while (q--)
{
int ans = 0;
scanf("%lf%lf%lf%lf", &b.x, &b.y, &b.xx, &b.yy);
b.flag = (b.yy - b.y) / (b.xx - b.x);
for (i = 1;i <= n;i++)
if (fabs(b.flag - a[i].flag) <= eps)
ans++;
printf("%d\n", ans);
}
}
return 0;
}推荐阅读