Codeforces Round 928 (Div. 4) (A-E)

比赛地址 : 

https://codeforces.com/contest/1926

A 

遍历每一个字符串，比较1和0的数量即可，那个大输出那个;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
 
using namespace std;
 
inline void solve(){
	int n ; cin >> n ;
	for(int i=1;i<=n;i++){
		string s ; cin >> s ;
		int t = 0 ;
		for(char c : s){
			if(c=='A') t++;
		}
		if(t>=3) cout << "A" << endl;
		else cout << "B" << endl;
	}
}
 
signed main()
{
    IOS
    int _ = 1;
    // cin >> _;
    while(_ --) solve();
    return 0;
}

B . 

模拟，先找第一个出现的'1' , 然后求这一列1的个数(也就是正方形的一条边) : n，然后求'1'的总个数: s，判断n*n==s && 右下角那个点也是1,就能够判断是不是正方形，否则就是三角形 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
 
using namespace std;
 
char a[13][13] ;
 
inline void solve() {
	int n ; cin >> n ;
	int t = 0 ;
	bool tag = true;
	int x = 0 , y = 0 ;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin >> a[i][j] ;
			if(a[i][j]=='1' && tag){
				x = i ;
				y = j ;
				tag = false ;
			}
			if(a[i][j] == '1') t++;
		}
	}
	bool st = false ;
	int b = 0 ;
	for(int j=y;j<=n;j++){
		if(a[x][j]=='1') b++;// 长度		
	}
	if(x+b-1<=n&&y+b-1<=n&&a[x+b-1][y+b-1]=='1') st = true ;
	if(t==b*b && st) cout << "SQUARE" << endl;
	else cout << "TRIANGLE" << endl ;
	
}
 
signed main()
{
    IOS
        int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

C

前缀和 + 预处理

可以通过前缀和进行预处理，为O(2e5+n),然后对于每一个数据，都能够通过O(1)进行输出 ;

#include<bits/stdc++.h>
using namespace std;
typedef long long LL ;
const int N = 2e5 + 10 ;
LL a[N] ;
 
int get(int x){
	int t = 0 ;
	while(x) t+=x%10,x/=10;
	return t ;
}
 
void init(){
	a[1] = 1 ;
	for(int i=2;i<=2e5;i++){
		a[i] = a[i-1] + get(i) ;
	}
}
 
int main() {
	int tt ; cin >> tt ;
	init() ;
	while(tt--){
		int n ; cin >> n ;
		cout << a[n] << endl;
	}
	return 0 ;
}

数学 推式子

分情况讨论，推出数学式子 ， 然后算出答案 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
 
using namespace std;
 
LL get0(int n){
	LL ans = (n+1)*n/2 ;
	return ans ;
}
LL get1(int n){
			int x = n / 10 ;
		int y = n % 10 ;
		LL t = x * (x-1) / 2 * 10 + 45 * x + get0(y) + (y+1) * x;
		return t ;
}
 
LL get2(int n){
	int x = n / 100 ;
		int y = n % 100 ;
		LL t = get1(y) + x * (x-1) / 2 * 100 + x * get1(99) + (y+1) * x;
		return t ;
}
LL get3(int n){
	int x = n / 1000 ;
		int y = n % 1000 ;
		LL t = get2(y) + x * (x-1) / 2 * 1000 + x * get2(999) + (y+1) * x;
		return t ;
}
LL get4(int n){
	int x = n / 10000 ;
		int y = n % 10000 ;
		LL t = get3(y) + x * (x-1) / 2 * 10000 + x * get3(9999) + (y+1) * x;
		return t ;
}
 
inline void solve(){
	int n ; cin >> n ;
	if(n<10) {
		cout << (n+1)*n/2 << endl;
		return ;
	}
	if(n>=10 && n<100){
		int x = n / 10 ;
		int y = n % 10 ;
		LL t = x * (x-1) / 2 * 10 + 45 * x + get0(y) + (y+1) * x;
		cout << t << endl;
		return ;
	}
	if(n>=100 && n<1000){
		int x = n / 100 ;
		int y = n % 100 ;
		LL t = get1(y) + x * (x-1) / 2 * 100 + x * get1(99) + (y+1) * x;
		cout << t << endl;
		return ;
	}
	if(n>=1000 && n<10000){
		int x = n / 1000 ;
		int y = n % 1000 ;
		LL t = get2(y) + x * (x-1) / 2 * 1000 + x * get2(999) + (y+1) * x;
		cout << t << endl;
		return ;
	}
	if(n>=10000 && n<100000){
		int x = n / 10000 ;
		int y = n % 10000 ;
		LL t = get3(y) + x * (x-1) / 2 * 10000 + x * get3(9999) + (y+1) * x;
		cout << t << endl;
		return ;
	}
	if(n>=100000 && n<1000000){
		int x = n / 100000 ;
		int y = n % 100000 ;
		LL t = get4(y) + x * (x-1) / 2 * 100000 + x * get4(99999) + (y+1) * x;
		cout << t << endl;
		return ;
	}
}
 
signed main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}

D

哈希表 + 位运算

对于每个数来说，能与它一组的有且仅有二进制在低31位上的31位都完全相反这一个数，那么可以得到一个组最多两个数字，对于x,那么能够与它配对的数字也就是 : ((1<<31)-1) ^ x ,其中((1<<31)-1)代表2^31-1,其二进制的低31位全是一；

通过上面就可以一遍遍历，用map记录之前出现过的数，遇到能匹配的，就删掉一个 ;

int yy = (1<<31) - 1 ;
/ 一对中的所有位都不同的条件等价于当我们对 2个数进行异或时，该对产生的数的所有位都设置为 1
inline void solve2(){
	int n ; cin >> n ;
	map<int,int> mp ;
	int ans = 0 ;
	for(int i=1;i<=n;i++){
		int x ; cin >> x ;
		if(!mp[x]) ++ans,++mp[yy^x];
		else --mp[x] ;
	}
	cout << ans << endl ;
}

哈希表 + 字符串

如果不精通位运算，就可以直接采取hash表存字符串的方式；

这里采用set + map进行模拟 ;

LL a[N] ;
 
string get(string s){
	string str = "" ;
	for(char c : s) str += c == '1' ? '0' : '1' ;
	return str;
}
 
 
inline void solve(){
	int n ; cin >> n ;
	for(int i=1;i<=n;i++) cin >> a[i] ;
	set<string> st ;
	map<string,int> mp ;
	int x = 0 ;
	for(int i=1;i<=n;i++){
		string s = bitset<32>(a[i]).to_string();
		s = s.substr(1);
		string str = get(s) ;
		if(st.count(str)){
			x++;
			if(mp[str]>1){
				mp[str]--;
			}else{
				st.erase(str);
				mp[str]--;
			}
		}else{
			st.insert(s) ;
			mp[s]++;	
		}  
	}
	cout << n - x << endl ;
}

E

思维题

对于第一轮，就已经把全部的奇数放完了，那么之后的就全部都是偶数 ;

永远不会在非2的幂的棋步上放下棋 ，因为非2的幂的步上，一定包含一个奇数因子，会在第一轮就被放下 ；

加入上一步还剩n个棋子，那么下一步一定会下其中的一半棋子，然后模拟就好了 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
 
using namespace std;
 
// 第一轮 把奇数放完了，后面一定全是偶数
// 永远不会在非2的幂的棋步上放下棋 ，因为非2的幂的步上，一定包含一个奇数因子，会在第一轮就被放下 ；
  
 
void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> v;
	while (n) {
		v.push_back((n + 1) / 2); //每次放奇数个 
		n /= 2;
	}
	int tot = 0, pow2 = 1;
	for (int x : v) {
		if (tot < k && k <= tot + x) {
			cout << pow2 * (2 * (k - tot) - 1) << '\n';
			return;
		}
		tot += x;
		pow2 *= 2;
	}
}
 
signed main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}