84分蒟蒻求大佬帮调(时间空间没爆,但是排了三天,wa哭了…)
查看原帖
84分蒟蒻求大佬帮调(时间空间没爆,但是排了三天,wa哭了…)
563650
haochengw920楼主2022/10/14 19:18
//84分蒟蒻求大佬帮排错
//时间空间没爆,但是wa的是最后两个点
//调三天了哇…求大佬帮助
//码风比较差,注释的也不好,大佬轻喷
//(来自灰名蒟蒻的心酸啊…) 
#include<cstdio>
#include<cctype>
#include<cstring>
#include<utility>
#include<vector>
#include<algorithm>
#define ll long long
#define mkp make_pair
#define pb push_back
#define Pos pair<int, int>
#define Tup pair<Pos, int>
#define fir first
#define sec second
using namespace std;

inline Tup mkt(int x, int y, int z){return mkp(mkp(x, y), z);}
inline int read()
{
		int x = 0, f = 1; char c = getchar();
		while (!isdigit(c)){if (c == '-') f = -1; c = getchar();}
		while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
		x *= f; return x;
}
inline void write(ll x)
{
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar (x % 10 + '0');
}

const int MAXN = 45;
vector<Pos>v;//指令 
vector<Tup>v1, v2;//前一半和后一半指令从零开始分别能搜到的位置 
int n, xg, yg;
int nn;//n >> 1 
int len1, len2;//v1、v2的长度 
ll ans[MAXN], s1[MAXN], s2[MAXN];//答案,v1、v2中Pos相同时k = i的重复数量(后面双指针时使用) 

inline void dfs1(int step, int k, int sumx, int sumy)//前一半指令从零搜(前后只有两段,就写成两个函数了) 
{
		if (step == nn + 1)
		{
				v1.pb(mkt(sumx, sumy, k));
				return; 
		}
		dfs1(step + 1, k + 1, sumx + v[step].fir, sumy + v[step].sec);
		dfs1(step + 1, k, sumx, sumy);
}

inline void dfs2(int step, int k, int sumx, int sumy)//后一半 
{
		if (step == nn)
		{
				v2.pb(mkt(sumx, sumy, k));
				return;
		}
		dfs2(step - 1, k + 1, sumx + v[step].fir, sumy + v[step].sec);
		dfs2(step - 1, k, sumx, sumy);
}

int main()
{
		n = read(); xg = read(); yg = read();
		for (int i = 0; i < n; ++ i)
		{
				int xi, yi;
				xi = read(); yi = read();
				v.pb(mkp(xi, yi));
		}
		nn = n >> 1;//输入 
		
		dfs1(0, 0, 0, 0);
		dfs2(n - 1, 0, 0, 0);
		
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());//排序,方便后面的双指针 
		
		len1 = v1.size(); len2 = v2.size();
		
		for (int i = 0, j = len2 - 1; i < len1 && j >= 0;)
		{
				int x1 = v1[i].fir.fir, x2 = v2[j].fir.fir, y1 = v1[i].fir.sec, y2 = v2[j].fir.sec, k1 = v1[i].sec, k2 = v2[j].sec;
				
				if (x1 + x2 < xg || (x1 + x2 == xg && y1 + y2 < yg)) i ++;//偏小的情况,因为i从零开始,j从len2 - 1开始, 只能通过增加i加大总位置值 
				else if (x1 + x2 > xg || (x1 + x2 == xg && y1 + y2 > yg)) j --;//偏大 
				
				else {
						memset (s1, 0, sizeof(s1));
						memset (s2, 0, sizeof(s2));//清空 
						
						for (; i < len1 && mkp(x1, y1) == v1[i].fir; ++ i) s1[v1[i].sec] ++;//v1中的重复 
						for (; j >= 0 && mkp(x2, y2) == v2[j].fir; -- j) s2[v2[j].sec] ++;//v2 
						
						for (int k1 = 0; k1 <= nn + 1; ++ k1)
								for (int k2 = 0; k2 <= nn + 1; ++ k2)
										ans[k1 + k2] += s1[k1] * s2[k2];//乘法原理 
				}
		}
		
		for (int i = 1; i <= n; ++ i) write(ans[i]), putchar('\n');//输出 
		
		return 0;
}
2022/10/14 19:18
加载中...