[UOJ 113][UER #2]手机的生产

神哎……

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

考虑从左往右计算某一段。如果有一个手机某一段运算结果为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;
}

[UOJ 21][UR #1]缩进优化

神题啊……

考虑让答案最小不好做,那么我们想,把连续的一段空格变成一个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;
}

[CF 676B]Pyramid of Glasses

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

我们可以直接把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;
}