比赛地址 :
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;
}
