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()
{IOSint _ = 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()
{IOSint _ = 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()
{IOSint _ = 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()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}