A. Antiamuny wants to learn binary search
签到题.
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e9 + 10, mod = 1e9 +7;
//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<char, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
string s;
vector<PII> a,ans;
int f(int l,int r,int x) { // l <= x <= r
int cnt = 0;
while(l <= r) {
cnt++;
int mid = (l + r) / 2;
if (mid == x) break;
if (mid < x) l = mid + 1;
else r = mid - 1;
}
return cnt;
}
void solve()
{
cin >> n >> m >> k;
cout << f(n,m,k) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int Ke_scholar = 1;
cin >> Ke_scholar ;
while(Ke_scholar--)
solve();
return 0;
}
View Code
B. Bespread with chequers
用dp数组来代表n列时的方案总数,可以发现n是偶数时,dp[n] = dp[n - 1] + 1, 奇数时dp[n] = dp[n - 1] - 1,别忘了取模.
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 10,mod = 1e9 + 7;
int n, m, x;
int dp[N];
void init(){
dp[1] = 1;
for(int i = 2;i < 1e6 + 10;i ++){
if(i & 1)
dp[i] = (2 * dp[i - 1] % mod - 1) % mod;
else
dp[i] = (2 * dp[i - 1] % mod + 1) % mod;
}
}
void solve() {
cin >> n;
cout << dp[n] % mod << endl;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int h_h;
init();
cin >> h_h;
//h_h = 1;
for(int i=1;i<=h_h;i++)solve();
return 0;
}
View Code
C.Converse the string
即就是对字符串s遍历一遍,用s[i]和字符串ans的首字符比较,字典序小的放前面,反之放后面.
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6+10, mod = 1e9 + 7;
//typedef long long ll;
typedef pair<int,int> PII;
int n,m,t,k;
map<int,int> mp;
priority_queue<int> QQ;
deque<int> Q;
void solve() {
string s;
cin >> s;
deque<char> ans,ori;
for(auto i : s)
if(ans.empty())
ans.push_back(i);
else{
if(i <= ans.front()){
ans.push_front(i);
}
else{
ans.push_back(i);
}
}
for(auto i : ans){
cout << i ;
}
cout << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int Ke_scholar = 1;
cin >> Ke_scholar;
while(Ke_scholar--)
solve();
return 0;
}
/*
*/
View Code
G.Golden jade matrix checker
二维前缀和,对给出x,y矩阵,去原矩阵中找他的和即可,大于等于0的直接输出No即可.
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
using namespace std;
const int N = 2010;
const int M = 20;
int a[N][N];
void solve() {
int n, m, x, y;
cin >> n >> m >> x >> y;
vector<vector<int>> s(n + 1,vector<int> (m + 1,0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
if (s[n][m] <= 0) {
cout << "NO" << endl;
return;
}
for(int i = 1;i <= n - x + 1;i ++){
for(int j = 1;j <= m - y + 1;j++){
int dx = i + x, dy = j + y;
int res = s[dx - 1][dy - 1] - s[dx-1][j - 1] - s[i - 1][dy-1] + s[i - 1][j - 1];
if(res >= 0){
cout << "NO" << endl;
return ;
}
}
}
cout << "YES" << endl;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int h_h;
cin >> h_h;
//h_h = 1;
while (h_h--)solve();
return 0;
}
View Code
H.How to know the function
很容易能找出,只有n为0时一次即可,其余次数均可以2次求出,记得开longlong.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 501;
long long n,m,x;
char mp[N][N];
int main(){
int T;
cin>>T;
while(T--){
cin >> n;
if( n == 0){
cout << 1 << endl;
}
else {
cout << 2 << endl;
}
}
return 0;
}
View Code
J. Juxtaposed brackets
由定义可知,每个()里最多包含两个并列的括号,被括号包含的括号算是一个,例如(()()),外面的括号就是包含了两个并列的,而((()))这样只算包含了一个,如此,我们可以开一个数组去记录每一个括号内包含了多少个并列的括号,其中不对称,或者左扩右扩不相等的都可以做个标记,之后输出NO即可,对付符合要求的,再对数组进行遍历,若有大于2的则说明有括号包含了2个以上的并列括号,输出NO.
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e9 + 10, mod = 1e9 +7;
//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<char, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
string s;
vector<PII> a,ans;
void solve()
{
string s;
cin >> s;
bool f = false;
vector<int> a(s.size());
stack<int> st;
for(int i = 0;i < s.size();i ++){
if(s[i] == '('){
st.push(i);
}
else if(st.empty()){
f = true;
break;
}
else {
st.pop();
if(st.size())
a[st.top()]++;
}
if(st.empty() && i < s.size() - 1){
f = true;
break;
}
}
for(auto i : a){
if(i > 2){
f = true;
break;
}
}
if(f || st.size()){
cout << "NO" << endl;
}
else
cout << "YES" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int Ke_scholar = 1;
cin >> Ke_scholar ;
while(Ke_scholar--)
solve();
return 0;
}
View Code
标签：21,Contest,int,Spring,long,mod,include,dp,define From： https://www.cnblogs.com/Kescholar/p/17450256.html