正文索引 [隐藏]

日常爆零，平生夙愿是不要再爆了。比赛传送门→

A大吉大利

题目
给定n(<1e5)个整数a1,a2,…,an，计算

“&”为位与运算符

输入
第一行一个整数n.
第二行n个整数ai​.

输出
一个整数表示上述求和式的答案.

样例

样例输入
5
1 2 3 4 5
样例输出
33

赛时写了一个很老实的循环，果不其然T了。这时候基础不牢就地动山摇啊，硬是没想出来巧解，还是赛后去研究的，哎。

考虑到位与运算的特性，将样例化为二进制来分析：

0 0 1
0 1 0
0 1 1
1 0 0
1 0 1

根据题意计算，以右起第一列为例，第一个1与所有的1位与得到3，第二个1与所有的1位与也得到3….就这样得到了3个3也就是9。显然，对于数据中所有整数的第i位，运算结果就是1的个数的平方。

即，设有t[i]个数在二进制下的第i位为1，那么答案就会累加t2[i]个二进制下的1。所以就转化为了求：

因为答案以十进制输出，所以最后还要按位权乘2的i次幂转回10进制。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

typedef long long ll;

const int INF = 0X7F7F7F7F;
const int LIM = 32;

int n;
ll ans;
int a[LIM];

int main()
{
	get(n);
	rep(i, 1, n)
	{
		int num;
		get(num);
		int cnt = 0;
		while(num)//取出每一个数二进制下的每一位 
		{
			a[cnt++] += num % 2;//第cnt位累加 
			num /= 2;
		}
	}
	for (int i = 0; i < LIM; i++)
		ans += 1ll * a[i] * a[i] * (1 << i);//从0开始按位权转换 
	cout << ans;
	return 0;
}

B三角形周长和

题目
给定平面上n个点的坐标,并且我们定义两个点的距离为曼哈顿距离.曼哈顿距离是指对两个点(x1,y1),,他们之间的距离为∣x2−x1∣+∣y2−y1∣。
众所周知三个点可以构成一个三角形,那么n个点可以构成C(n,3)​个三角形,现在你需要求出所有三角形的周长和。输出在模998244353意义下的答案.数据保证不存在三点共线.

输入
第一行一个整数表示n.
接下来n行每行两个整数x,y表示一个点.

输出
一个整数表示周长和

样例

样例输入
3
0 0
1 0
1 1
样例输出
4

这题其实就是一道纯思维题。 真的差一点点就A了，死在草稿纸太乱，哎，还是人菜了。

假设有5个点，编号为1,2,3,4,5。根据组合数原理，一共有以下几种组合：
1-2-3, 1-2-4, 1-2-5, 1-3-4, 1-3-5, 1-4-5;
2-3-4, 2-3-5, 2-4-5;
3-4-5.

两点连成一条边，那么1-2就是第一条边，可以很清晰的看见一共计算了3次1-2边。事实上，每一条边都算了三次，这很容易数出来。

那么不难总结出：对任意的n个点，他们两两连成的边在这道题里会被计算n-2次。这就是答案。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

typedef long long ll;

const int INF = 0X7F7F7F7F;
const int LIM = 3333+5;
const ll MOD = 998244353;

int n;
ll ans;
ll x[LIM], y[LIM];

int main()
{
	get(n);
	rep(i, 1, n) 
	{ 
		lget(x[i]); 
		lget(y[i]); 
	}
	rep(i, 1, n) rep(j, i, n)
	{
		ans += (abs(x[i] - x[j]) + abs(y[i] - y[j])) * (n-2) % MOD;
		ans %= MOD;
	} 
	cout << ans;
	return 0;
}

值得一提的是，这题的点要用LL来存，不然只能过60%。题目里明明白白给出来的1e9怎么就不作数了呢，真是奇怪。

C操作集锦

题目
有一款自走棋有26种操作,每种操作我们都用a,b,c,d,…,x,y,z的符号来代替.
现在牛牛有一个长度为n的操作序列,他现在可以从里面拿出某些操作来组合成一个操作视频, 比如说操作序列是abcd,那么操作视频就有a,b,c,d,ab,ac,ad等(也就是操作序列的子序列).他现在想知道长度为k且本质不同的操作视频有多少种.
比如对于abab，长度为2且本质不同的结果有ab,aa,ba,bb。
考虑到答案可能非常大,你只需要输出在模1e9+7意义下的答案就可以了.

输入
第一行两个整数n,k.(1<=n<=1e3, 0<=k<=n)
第二行一个长度为n的字符串,保证只存在小写字母.

输出
一行一个整数表示长度为k且本质不同的操作视频的个数. 

样例

样例输入
3 1
abc
样例输出
3

题目就是求长度为k的所有本质不同子序列，很容易可以想到dp。

很有趣的是，这题存在一个k为0的点，可以特判一手。