牛客练习赛/挑战赛题

牛客练习赛72

https://ac.nowcoder.com/acm/contest/8282#question

A-brz的杯子：动手找规律

思路: 找规律

1：1，2：1，3：1，4：1 2，5：1，6：1 2 3， 7：1，8：1 2 4 ......16：1 2 4 8

可以看出需要的个数最大只在1 2 4 8 16 .... 这些数变化，也就是说1-n需要数的个数的最大为n的二进制位数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

int solve(int x)
{
	int cnt = 0;
	while(x){
		x >>= 1;
		cnt++;
	}
	return cnt;
}

int main()
{
	int t,n,m,ans = 0;
	scanf("%d",&t);
	for(int i = 1; i <= t; i++){
	    scanf("%d%d",&n,&m);
	    int t = solve(n);
	    if(t > m){
	    	ans ^= (i-1);
		}
		else ans ^= (i);
	}
	printf("%d\n",ans);
	return 0;
}

B-brz的雪糕：前缀和

思路：前缀和，sum[i]表示1-i中能增加的愉悦数，l-r愉悦数就是sum[r] - sum[l-1] + (a[l] == a[l-1]?1:0)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

int a[2000005],sum[2000005];
int main()
{
	int n,k,q,l,r;
	scanf("%d%d%d",&n,&k,&q);
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
	}
	//sum[1] = 1;
	for(int i = 1; i <= n; i++){
		if(a[i] != a[i-1]){
			sum[i] = sum[i-1]+1;
		}
		else sum[i] = sum[i-1];
	}
	while(q--){
		scanf("%d%d",&l,&r);
		int cnt = 0;
		cnt = sum[r] - sum[l-1];
		if(a[l] == a[l-1]) cnt++;
		cnt >= k ? printf("Yes\n") : printf("No\n");
	}
	return 0;
}

牛客练习赛68

https://ac.nowcoder.com/acm/contest/7079

A-牛牛的mex：前缀后缀

https://ac.nowcoder.com/acm/contest/7079/A

思路：因为数为1-n的数，所有先初始化前缀最小值和后缀最小值，然后取min(pre[l-1],suf[r+1]),注意边界。

#include <bits/stdc++.h>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
using namespace std;

int pre[100005],suf[100005],a[100005];
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
	pre[0] = n;
	for(int i = 1; i <= n; i++) pre[i] = min(pre[i-1],a[i]);
	suf[n+1] = n;
	for(int i = n; i >= 1; i--) suf[i] = min(suf[i+1],a[i]);
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		int mex = min(pre[l-1],suf[r+1]);
		printf("%d\n",mex);
	}
	return 0;
}

牛客练习赛59

https://ac.nowcoder.com/acm/contest/4743

B-牛能和小镇：最小生成树(公式变形)

https://ac.nowcoder.com/acm/contest/4743/B

思路：

公式变换一下， $(x_{1}^{2}y_{1}+y_{1}^{3}-2x_{1}y_{1}^{2})-(x_{2}^{2}y_{2}+y_{2}^{3}-2x_{2}y_{2}^{2})$

令a1= $x_{1}^{2}y_{1}+y_{1}^{3}-2x_{1}y_{1}^{2}$

两点距离为|ai-aj|

对于每个点求出ai，然后从小到大排序，因为要求最小值，相邻两点连接求距离就是最小值。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

ll a[100005];
int main()
{
	int n,x,y;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d",&x,&y);
		a[i] = 1ll*x*x*y+1ll*y*y*y-1ll*x*y*y*2;
	}
	sort(a+1,a+n+1);
	ll ans = 0;
	for(int i = 1; i < n; i++){
		ans += a[i+1] - a[i];
	}
	printf("%lld\n",ans);
 	return 0;
}

D-取石子游戏：找规律

https://ac.nowcoder.com/acm/contest/4743/D

思路：

、

从图可以中可以找到规律，小灰灰的必胜态和必败态是在某个区间内出现，并且这些区间的左右端点都是有规律的，必胜态区间的左端点*2为下一必败态区间的左端点，必败态左端点*2-1为下一必胜态区间左端点，预处理出这些区间的端点，发现这些区间的个数不大，所有对于给出的n，直接暴力判断n在哪个区间即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

ll ran[1000005];
int main()
{
	int l = 2,r = 3,cnt = 2;
	ran[0] = 1;
	ran[1] = 2;
	while(ran[cnt-1] <= 1e18){
		if(!(cnt&1)){
			ran[cnt] = ran[cnt-1]*2;
		}
		else{
			ran[cnt] = ran[cnt-1]*2-1;
		}
		cnt++;
	}
	int t;
	ll n;
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&n);
		for(int i = 0; i <= cnt; i++){
			if(ran[i] > n){
				if(!((i-1)&1)){
					printf("XiaoQiao\n");
				}
				else{
					printf("XiaoHuiHui\n");
				}
				break;
			}
		}
	}
 	return 0;
}

牛客练习赛58

https://ac.nowcoder.com/acm/contest/4090#question

D-迷宫：动态规划

https://ac.nowcoder.com/acm/contest/4090/D

思路：

先看牛妹走迷宫的策略，可以发现要想从(1,1)走到(n,m)，那么牛妹只能往右走，不能往右走的情况下才往下走，不可能往上走或往左走。

理由：

不能往左走，因为往左走说明当前位置右边有障碍，走完之后到达某个位置，那这个位置右边就会有一个空位，按照策略牛妹会往右走，这样会往复横跳，导致不能走下去了。

不能往上走，能往上走说明当前位置的右边和下面都有障碍，而到当前位置来可能是从上面或者从右边过来，从上面过来说明上面的右边有障碍，上去了还得下来，同样是上下走动，从右边过来说明可以往左边走，不可能。综上所述，不能往上和往左走。

走格子，又是求最小值，想到用动态规划来做。

找状态：dp[i]][j] 表示到位置(i,j)的障碍最少增加数。

状态转移：dp[i][i] = min(dp[i][j],dp[i][j-1]) 从右边过来，不用加障碍物

dp[i][j] = min(dp[i][j],dp[i-1][j]+(s[i-1][j+1] == '0' ? 1 : 0) ) 从上面过来，因为优先往右边走，所有如果上面的右边有格子，那么要加上一个障碍物。

赋初值： dp[1...n][1....m]=inf, dp[1][1] = 0

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int dp[1005][1005];
char s[1005][1005];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++){
		scanf("%s",s[i]+1);
	}
	//优先往右，不能往右再往下走。 
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= m; j++) dp[i][j] = 10000000;
	}
	dp[1][1] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(s[i][j] == '1') continue;
			dp[i][j] = min(dp[i][j],dp[i][j-1]);
			if(s[i-1][j+1] == '0') dp[i][j] = min(dp[i][j],dp[i-1][j]+1);
			else dp[i][j] = min(dp[i][j],dp[i-1][j]);
		} 
	}
//	for(int i = 1; i<= n; i++){
//		for(int j  =1; j <= m; j++){
//			cout << dp[i][j] << " ";
//		}
//		cout << endl;
//	}
	if(dp[n][m] == 10000000) printf("-1");
	else printf("%d\n",dp[n][m]);
 	return 0;
}

牛客挑战赛45

https://ac.nowcoder.com/acm/contest/8563

B-我是A题

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 998244353 ;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
  
using namespace std;

struct node{
	int v,next;
	ll w;
}edge[10000005];

ll w[1000005];
int head[1000005],cnt = 0;
void add(int u,int v,ll w)
{
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

ll ans = 0;
int n,k;
void init()
{
	for(int i = 0; i <= n; i++) head[i] = -1;
}

void dfs(int s,int fa)
{
	for(int i = head[s]; ~i; i = edge[i].next){
		int v = edge[i].v;
		if(v == fa) continue;
		dfs(v,s);
		ll W = edge[i].w;
		w[s] = (w[s]+w[v])%k;
		if(w[v]) ans += W;
	}
}

int main()
{
	
	cin >> n >> k;
	init();
	int u,v,val;
	for(int i = 1; i <= n; i++) cin >> w[i],w[i]%=k;
	for(int i = 1; i < n; i++){
		cin >> u >> v >> val;
		add(u,v,val);
		add(v,u,val);
	}
	dfs(1,0);
	cout << ans;
	return 0;
}