Accelerator‘s Blog

T1：统计满足Ai mod Ci != 0且Ai & Ai+1 = 0的序列Ai数量。
    Hint:20%的数据 N=10，M=2；另有40%的数据N=50，M=5；剩余的数据N=50，M=15。
Solutions:
    20分算法：暴力搜索即可；
    60分算法：据说还有暴力方法可以拿到60分。
    100分算法：学长推倒出了神奇的矩阵：可以用于表示出对于序列中的第k个元素取i值d[i] = j，j为可行方案数量。

如图所示是一个4*4的该矩阵，横行i表示第k个元素可以取的i值d[i]，纵列表示取d[i]时产生的解的数量，现在要做的实际上是通过这样一个4*4的子矩阵利用Dp求出一个2^m*2^m的矩阵。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 50 + 5
#define M 1 << 15
#define Mod 1000000000

int n, m, ans, C[N], Dp[M], Dp2[M];

inline int add(int a, int b)
{
    return a + b - (a + b >= Mod ? Mod : 0);
}
inline void solve(int l, int r)
{
    if (l == r - 1)
    {
        Dp2[l] = Dp[l];
        return ;
    }
    int mid = l + r >> 1;
    solve(l, mid);
    solve(mid, r);
    for (int i = l; i < mid; i ++)
    {
        int t = Dp2[i];
        Dp2[i] = add(Dp2[i], Dp2[i + mid - l]);
        Dp2[i + mid - l] = t;
    }
}
int main(){
    freopen("tle.in", "r", stdin);
    freopen("tle.out", "w", stdout);
    
	scanf("%d%d", &n, &m);
    for (int i = n - 1; i >= 0; i --)
        scanf("%d",  &C[i]);
    Dp[0] = 1;
	while (n --)
    {
        solve(0, 1 << m);
        for (int i = 0; i < (1 << m); i ++)
            Dp[i] = i % C[n] ? Dp2[i] : 0, Dp2[i] = 0;
    }
	for(int i = 0;i < (1 << m); i ++)
		ans = add(ans,Dp[i]);
	printf("%d\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2：题目背景略（Lovelive= =）
       给出n个操作，每个操作含t，x，y。t =1维护：增加一个元素，smile值为x，pure值为y；t = 0维护：询问对于一首歌曲

(p,q)；最大的和适度：ans = p*x + q*y；t=-1维护：删除smile值为x，pure值为y的元素。
     Hint：有40%的数据n=1000；有40%的数据n=15000；剩下的数据n=50000。
Solutions:
    100分算法I：裸暴力，用数组维护内存会大一些，若用动态链表维护内存就更大了，貌似数组比链表快？
    100分算法II：转化为计算几何问题，用分块 +　凸包处理（表示不会）。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 50000 + 5
#define INF 1000000000
int n,vis = 0,t;
long long p,q;
struct Node{
	ll x,y;
	bool ok;
}a[maxn];

int main()
{
	//freopen("ll.in","r",stdin);
	//freopen("ll.out","w",stdout);
	memset(a,0,sizeof(a));
	scanf("%d",&n);
	for(int i = 1;i <= n; i++){
		scanf("%d%lld%lld",&t,&p,&q);
		if(t == 1){
			a[vis].x = p;
			a[vis].y = q;
			a[vis].ok = 1;
			vis ++;
		}
		if(t == 0){
			ll Max = -INF;
			for(int i = 0;i < vis; i++)
				if(a[i].ok && (p*a[i].x + q*a[i].y)>Max)Max = p*a[i].x + q*a[i].y;
			printf("%lld\n",Max);
		}
		if(t == -1){
			for(int i = 0;i < vis; i++)
				if(a[i].x==p && a[i].y==q){
					a[i].ok = 0;break;
				}
		}
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

T3：两个人（Alice、Bob）取巧克力，每个巧克力有一个能量等级r和可口度s。两个人也各有一个能量等级A、B，每个人有

Eat和Pass两种操作，Pass操作会消耗能量等级。若两人足够聪明，求巧克力取完是两人的满足度（吃到巧克力可口度的和）。
    Hint:其中有30%的数据1≤N≤10, 0≤A,B,r≤1,000,000,000
           另外有30%的数据1≤N≤50, 0≤A,B,r≤10
           剩下的数据1≤N≤150, 0≤A,B,r≤1,000,000,000
           对于所有的数据满足0≤s, 且s的和小于150
Sulotions:
    30分算法：直接搜索所有可能的状态，对于大数据TLE是必然（100个测试点的题目也是罕见= =）。
    100分算法：DP，对Alice和Bob分别建立两个状态图，从Alice和Bob的角度分别DP一次，再维护最优解（对于多维数组的函数，可以考虑使用模板（Template<Class T> T 函数名（T 变量......)）。（表示不会）看了一下std，感觉std那个方法就是模拟两人的操作过程再直接输出（其实这其中也有Dp的成分）？用F[i][j]表示状态：i表示第i块巧克力，j表示当前该人的能量等级，F[i][j]表示初始能量等级的最小值。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 150 + 5
typedef long long ll; 
#define INF 1LL<<60
int N,sum = 0,s[maxn];
ll A,B,r[maxn],tmp;
ll FA[maxn][maxn],FB[maxn][maxn];

template<class T> inline T &gmin(T &a,const T &b){
	if(a > b)a = b;return a;
}
template<class T> inline T &gmax(T &a,const T &b){
	if(a < b)a = b;return a;
}
/*Process of Alice's process
  For F[i][j]:i means the i-th chocolate;
  j means the person's present scores;
  and F[i][j] means the person's minnum enegy levels.
*/
inline void Alice(int i){
	for(int j = sum; j >= 0; j--){
		tmp = INF;
		gmin(tmp,FA[i][j + 1]);
		if(j >= s[i]) gmin(tmp, FB[i + 1][j - s[i]] - r[i]);
		gmin(tmp, max(1LL,FA[i + 1][j] + r[i] + 1));
		FA[i][j] = tmp;
	}
	return;
}
/*Process of Bob's process*/
inline void Bob(int i){
	for(int j = 0;j <= sum; j++){
		tmp = -INF;
		if(j)gmax(tmp,FB[i][j - 1]);
		gmax(tmp,FA[i+1][j] + r[i]);
		if(j >= s[i]) gmax(tmp, min(1LL,FB[i+1][j - s[i]] - r[i] - 1));
		FB[i][j] = tmp;
	}
	return;
}

int main(){
	freopen("sw.in","r",stdin);
	freopen("sw.out","w",stdout);
	
	scanf("%d%lld%lld",&N,&A,&B);
	for(int i = 0;i < N; i++){
		scanf("%lld%d",&r[i],&s[i]);
		sum += s[i];
	}
	for(int i = 0;i < maxn; i++)
		for(int j = 0;j < maxn; j++){
			FA[i][j] = INF;
			FB[i][j] = INF;
		}
	FA[N][0] = -INF;
	FB[N][0] = -INF;

	/*Process of the operations */
	for(int i = N; i--;){
		Alice(i);
		Bob(i);
	}
	
	int ans = 0;
	for(int i = 0;i <= sum; i++)
		if(FA[0][i] <= A-B) ans = i;
	printf("%d %d\n", ans, sum - ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

本次题目无论难度如何，爆零这种事发生既是令人不爽也是不能容忍的，尤其是第二题，这一次是因为把一个该做局部变量的

变量做全局变量。多次在这样的签到题上卡住也说明代码实现的一些细节没有搞清楚，然而正所谓细节决定成败，因此以后在

做题目的过程中要多注意这些细节。