danihao123's Blog

神哎……

既然与的优先级比或高，那么我们就可以用或把程序切成若干段，每一段的值决定了最后的取值。

考虑从左往右计算某一段。如果有一个手机某一段运算结果为0，那么它会继续往下运算，反之则会停止运算。

对于每一个在前\(i\)段的值都是0，然后开始跑第\(i + 1\)段的手机。他们都会额外产生\(l\)（这一段的fork个数）个手机，并且由于这些手机一被生产出来的返回值就是0，所以新的这些手机在这一段取值为0。而原来的老手机，在这一段的取值事1，于是之后的运算就不会接着做了。

这样一来，我们就可以动态维护在之前的段里的返回值全是0的手机，然后就可以做了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
const int maxn = 100005;
const ll ha = 998244353LL;

bool op[maxn];
int main() {
  std::vector<int> vec;
  int last = 0;
  int n; scanf("%d", &n);
  for(int i = 1; i <= (n - 1); i ++) {
    char buf[5]; scanf("%s", buf);
    if(buf[0] == '|') {
      vec.push_back(i - last);
      last = i;
    }
  }
  vec.push_back(n - last);
  ll pre0 = 1LL;
  ll ans = 1LL;
  for(auto x : vec) {
    ans += (pre0 * (ll(x))) % ha; ans %= ha;
    pre0 = (pre0 * (ll(x))) % ha;
  }
  printf("%lld\n", ans);
  return 0;
}

神题啊……

考虑让答案最小不好做，那么我们想，把连续的一段空格变成一个TAB（假设TAB长度为\(x\)）就是减少\(x - 1\)空格，那么我们尝试去最大化减小的空格的量。

然后考虑枚举\(x\)是啥，然后去算减少的空格的量。对于任意\(a_i\)，减少的空格量就是\((x-1)\lfloor\frac{a_i}{x}\rfloor\)，这似乎可以整除分块哎……

但是会被T掉。我们想，其实我们对任意\(x\)，我们去枚举\(\lfloor\frac{a_i}{x}\rfloor\)就行啦，要查询满足条件的\(a_i\)数量可以预处理一个权值前缀和然后就能\(O(1)\)做啦、

假设\(X = \max\{a_i\}\)，那么每一个\(x\)对时间复杂度的贡献就是\(O(\frac{X}{x})\)。这不就是调和级数吗？所以时间复杂度事\(O(X\ln X)\)。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
const int maxn = 1000005;
typedef long long ll;
int a[maxn], C[maxn];
int n, bd;
void process() {
  for(int i = 1; i <= n; i ++) {
    C[a[i]] ++;
  }
  for(int i = 1; i <= bd; i ++) {
    C[i] += C[i - 1];
  }
}
ll sum;
ll query(int x, int p) {
  int l = x * p;
  int r = x * (p + 1) - 1;
  if(r > bd) r = bd;
  return (C[r] - C[l - 1]);
}
ll calc(int x) {
  ll delta = 0;
  for(int i = 1; i <= (bd / x); i ++) {
    ll cnt = query(x, i);
    delta += (ll(i)) * cnt * (ll(x - 1));
  }
#ifdef LOCAL
  printf("ans of %d : %lld\n", x, sum - delta);
#endif
  return (sum - delta);
}

int main() {
  scanf("%d", &n);
  sum = 0LL; bd = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &a[i]);
    bd = std::max(bd, a[i]);
    sum += a[i];
  }
  process();
  ll ans = sum;
  for(int i = 1; i <= bd; i ++) {
    ans = std::min(ans, calc(i));
  }
  printf("%lld\n", ans);
  return 0;
}

这题可以直接模拟，貌似也可过。但复杂度很高。

我们可以直接把t个单位的酒放入第一个杯，然后向下溢出，以此类推，这样复杂度就很优秀了。

代码：

#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
	int i,ans=0;
	long double temp;
	if(x>n)
		return 0;
	for(i=1;i<=n;i++){
		if(k[x][i]>=1.0){
			ans++;
			if(k[x][i]>1.0 && x<n){
				temp=(k[x][i]-1.0)/2;
				k[x][i]=1.0;
				k[x+1][i]+=temp;
				k[x+1][i+1]+=temp;
			}
		}
	}
	return ans+call(x+1);
}
int main(){
	cin>>n>>k[1][1];
	cout<<call(1)<<endl;
	return 0;
}