review
AT193
将n个数从小到大排序，挨个输出
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
string a[105];
int n,m;
bool cmp(string x,string y){
return x+y>y+x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
cout<<a[i];
}
cout<<"\n";
return 0;
}
CF898D
将闹钟响的时间排序，枚举 \(i\)，如果 \(a_i\) 到 \(a_i + m\) 这个区间内有大于k 个闹钟的话，就贪心将后面的删去，直到这个区间内只有 k 个为止
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
const int N = 2e5 + 10, M = 1e6 + 10;
int n, m, k;
int a[N], cnt;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i];
sort(a + 1, a + n + 1);
deque<int> dq;
for (int i = 1; i <= n; ++i)
{
while (dq.size() && dq.front() <= a[i] - m)
dq.pop_front();
dq.push_back(a[i]);
while (dq.size() >= k)
++cnt, dq.pop_back();
}
cout << cnt << endl;
return 0;
}
//
CF898C
将每一个人的号码排序，判断是否存在后缀的情况，有就删，没有就保留
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 25;
map<string,vector<string> >mp;
bool cmp(string s1,string s2)
{
return s1<s2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
string name,ss;
for(int i=1; i<=n; i++)
{
cin>>name;
int m;
cin>>m;
while(m--)
{
cin>>ss;
reverse(ss.begin(),ss.end());//先翻转存入便于判断后缀
mp[name].push_back(ss);
}
}
cout<<mp.size()<<endl;
map<string,vector<string> >::iterator it;
for(it=mp.begin(); it!=mp.end(); it++)
{
string str[1000],ans[1000];
cout<<it->first<<" ";
vector<string>v=it->second;
int len=v.size();
for(int i=0; i<len; i++)
{
str[i]=v[i];
}
sort(str,str+len,cmp);
int i,j,k=0;
for(i=0; i<len; i++)
{
int temp,flag=0;
for(j=i+1; j<len; j++)
{
temp=str[j].find(str[i]);
if(temp==0)
{
flag=1;
break;
}
}
if(flag==0)
{
ans[++k]=str[i];
}
}
cout<<k;
for(int i=1; i<=k; i++)
{
reverse(ans[i].begin(),ans[i].end());
cout<<" "<<ans[i];
}
cout<<endl;
}
}
//
CF898B
枚举 \(x\) ，二分 \((n - a \times x) \mod b\) 是否等于 0
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 0;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,a,b;
cin>>n>>a>>b;
for(int i=0;i<=n/a;i++)
if((n - i * a) % b == 0)
{
cout<<"YES"<<endl;
cout<<i<<' '<<(n - a * i) / b;
return 0;
}
cout<<"NO";
return 0;
}
//
CF877E
用\(dfs\)序来找到子树，一个子树作为一段来建线段树
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
struct Tree
{
int l,r;
int turn;
int sum;
int mid;
} tr[N * 4];
vector<int> g[N];//存图
int in[N],out[N],order[N],times = 0;// 进入栈的时间，出栈的时间，dfs序，当前时间
void dfs(int root,int father)
{
in[root] = ++times;
order[times] = root;
int len = g[root].size();
for(int i=0; i<len; i++)
{
int v = g[root][i];
if(v == father) continue;
dfs(v,root);
}
out[root] = times;
}
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
if(tr[u].turn)
{
tr[u<<1].turn ^= 1, tr[u<<1|1].turn ^= 1;
tr[u<<1].sum = tr[u<<1].r - tr[u<<1].l + 1 - tr[u<<1].sum;// xor
tr[u<<1|1].sum = tr[u<<1|1].r - tr[u<<1|1].l + 1 - tr[u<<1|1].sum;// xor
tr[u].turn = 0;
}
}
int w[N];//原开关情况
void build(int u,int l,int r)
{
if(l == r) tr[u].l = l,tr[u].r = r,tr[u].turn = 0,tr[u].sum = w[order[l]];
else
{
tr[u].l = l,tr[u].r = r,tr[u].turn = 0;
int mid = l + r >> 1;
tr[u].mid = mid;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum = tr[u].r - tr[u].l + 1 - tr[u].sum; // xor
tr[u].turn ^= 1;
}
else
{
pushdown(u);
if(l <= tr[u].mid) modify(u<<1,l,r);
if(r > tr[u].mid) modify(u<<1|1,l,r);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].r < l || tr[u].l > r) return 0;
if(tr[u].l >= l && r >= tr[u].r) return tr[u].sum;
pushdown(u);
int res = 0;
if(l <= tr[u].mid) res += query(u<<1,l,r);
if(r > tr[u].mid) res += query(u<<1|1,l,r);
pushup(u);
return res;
}
int main()
{
int n;
cin>>n;
for(int i=2; i<=n; i++)
{
int x;
scanf("%d",&x);
g[x].push_back(i);
g[i].push_back(x);
}
for(int i=1; i<=n; i++) scanf("%d",&w[i]);
dfs(1,-1);
build(1,1,n);
int q;
scanf("%d",&q);
while(q--)
{
char opt[4];
int x;
scanf("%s%d",opt,&x);
if(opt[0] == 'p') modify(1,in[x],out[x]);
else cout << query(1,in[x],out[x]) << endl;
}
return 0;
}
//
CF787B
如果一个团队中没有出现绝对值相同的两个数，就是YES,否则NO
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 1e4+10;
unordered_map<int,int> t;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int k;
cin>>k;
t.clear();
bool flag = 0;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
t[x] = 1;
if(t[-x])
{
flag = 1;
}
}
if(!flag)
{
cout<<"YES";
return 0;
}
}
cout<<"NO";
return 0;
}
//
CF776B
质数为1，否则为2
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
bool st[N];
int prime[N],cnt=0;
void gets_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++] = i;
for(int j=0;prime[j] <= n/i;j++)
{
st[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}
return ;
}
int main()
{
int n;
cin>>n;
gets_prime(n+2);
if(n < 3) cout<<1<<endl;
else cout<<2<<endl;
for(int i=2;i<=n+1;i++)
{
if(st[i]) cout<<2<<' ';
else cout<<1<<' ';
}
return 0;
}
CF734C
考虑不用药，\(ans = n * w\)
考虑只用第一种药，如果\(b[i]\le s\)，就更新答案 \(ans = min(ans,n * a[i])\)
考虑只用第二种药，如果\(d[i]\le s\)，就更新答案 \(ans = min(ans,(n-c[i]))\)
考虑先用第一种药，再在d中二分出 \(x\) 为 \(s - b[i]\) 的位置， \(ans = min(ans, (n-c[x]) * a[i]\)
#include <bits/stdc++.h>
using namespace std;
const int INF= 0x3f3f3f3f;
const int N=2e5+5;
typedef long long LL;
LL n,m,k,w,s;
LL b[N],c[N];
struct Node
{
LL x;
LL y;
} a[N];
int main()
{
scanf("%d%d%d%d%d",&n,&m,&k,&w,&s);
for(int i=1; i<=m; i++) scanf("%d",&a[i].x);
for(int i=1; i<=m; i++) scanf("%d",&a[i].y);
for(int i=1; i<=k; i++) scanf("%d",&b[i]);
for(int i=1; i<=k; i++) scanf("%d",&c[i]);
LL time=n*w;
for(int i=1; i<=k; i++)
{
if(c[i] <= s)
{
time=min(time, (n-b[i])*w );
}
}
for(int i=1; i<=m; i++)
{
if(a[i].y <= s)
{
time=min(time, n*a[i].x );
}
}
for(int i=1; i<=m; i++)
{
if(a[i].y > s) continue;
LL aa=upper_bound(c+1,c+1+k, s-a[i].y )-(c+1);
if(c[aa] <= s-a[i].y)
time=min(time, (n-b[aa])*a[i].x) ;
}
cout<<time;
return 0;
}
CF898A
将一个数四舍五入。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 0;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
int a = n % 10;
int b = 10 - (n % 10);
if(a < b) cout<<n - a;
else cout<< n + b;
return 0;
}
//
CF811A
模拟，实在没啥可以解释的
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
int k = 1;
while(1)
{
if(a < k)
{
cout<<"Vladik"<<endl;
break;
}
a -= k;
k++;
if(b < k)
{
cout<<"Valera"<<endl;
break;
}
b -= k;
k ++;
}
return 0;
}
CF808A
所有的lucky year都可以表示为 \(j * 10^i\) ，枚举 \(i\) 和 \(j\) 即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
for(int i=1;;i*=10)
{
bool flag = 0;
for(int j=1;j<=9;j++)
{
if(i * j > n)
{
cout<<i*j-n<<endl;
flag = 1;
break;
}
}
if(flag) break;
}
return 0;
}
CF787A
枚举时刻 \(i\), 当 \((i - b) \mod a == 0 \; and \;(i - d) \mod c == 0\) 即输出i
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 0;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int a,b,c,d;
cin>>a>>b>>c>>d;
for(int i=0;i<=100000000;i++)
{
if(i-b >= 0 && i-d >= 0 && (i - b) % a == 0 && (i - d) % c == 0)
{
cout<<i;
return 0;
}
}
cout<<-1;
return 0;
}
//
CF786A
现在我们知道 1 是必败态，那么我们通过 \(DFS\) 可以判断每个点的胜负情况、是否有解。
我们考虑逆向思维，对每个玩家在 1 时的先手状态向前转移，具体过程如下：
- 定义 \(DFS(v,now)\) 表示现在是 \(now\)的位置，玩家 \(v\) 先手。
- 枚举上一次玩家 \(u\) 的操作 \(x\)，那么可以从 \(now-x\) 的位置转移到 \(now\) 的位置（注意这里的 \(now-x\) 不能等于 \(1\)）。
- 如果 \(now\) 的位置是必败态，那么根据结论：能转移到必败态的状态就是必胜态，可以得到 \(now-x\) 的位置是必胜态。
- 如果 \(now\) 的位置是必胜态，那么根据结论：只能转移到必胜态的状态就是必败态。我们记 \(cnt_{u,i}\) , \(i\) 表示在\(i\) 这个位置且 u 先手可以转移到的必胜态数量。当 \(cnt_{u,now-x}+1=k_u\),时，意味着从 \((u,now-x)\) 转移到的所有状态都是必胜态，那么意味着从 \((u,now-x)\) 这个状态为必败态。
- 继续 \(DFS(u,now-x)\) 进行转移即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 7005;
int k[2];
int cnt[2][N];
int step[2][N];
bool vis[2][N],win[2][N];
int n;
void dfs(int user,int pos)
{
if(vis[user][pos]) return ;
vis[user][pos] = 1;
int u = user ^ 1;
for(int i=1;i<=k[u];i++)
{
int pre = (pos - step[u][i] + n - 1) % n + 1;
if(pre == 1) continue;
if(!win[user][pos])
{
win[u][pre] = 1;
dfs(u,pre);
}
else if(++cnt[u][pre] == k[u])
{
win[u][pre] = 0;
dfs(u,pre);
}
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<=1;i++)
{
cin>>k[i];
for(int j=1;j<=k[i];j++)
cin>>step[i][j];
}
dfs(0,1);
dfs(1,1);
for(int i=0;i<=1;i++)
{
for(int j=2;j<=n;j++)
{
if(!vis[i][j]) cout<<"Loop ";
else if(win[i][j]) cout<<"Win ";
else cout<<"Lose ";
}
cout<<endl;
}
return 0;
}
//
CF701B
可以将车平移到四周，类似数学中的一块草地，要在上面铺路，求草地面积。
开个col,row数组记录这一列，行有没有被攻击。
如果新增的车的那一列，行没有攻击过，则n--，或m--
最后输出n * m
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
bool row[N];
bool col[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
long long num_row = n,num_col = n;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(!row[x]) row[x] = 1,num_row --;
if(!col[y]) col[y] = 1,num_col --;
cout<<num_row*num_col<<endl;
}
return 0;
}
//
CF701A
排序，a[i] 和 a[n - i + 1] 为一对
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
struct Node
{
int val;
int id;
bool operator < (const Node& x) const
{
return val < x.val;
}
}a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].val,a[i].id=i;
sort(a+1,a+1+n);
for(int i=1;i<=n/2;i++)
cout<<a[i].id<<' '<<a[n-i+1].id<<endl;
return 0;
}
CF664A
如果 a==b ，则为a，否则为1
#include <bits/stdc++.h>
using namespace std;
int main()
{
string a,b;
cin>>a>>b;
if(a==b) cout<<a;
else cout<<1;
return 0;
}
CF608B
处理出 b 的前缀和
如果a[i] == 1,就和b[i.i + n - 1]，ans 加上b中以i为左端点，长度为m的区间内0的个数
反之亦然
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 200005;
char a[N],b[N];
int sum[N];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>a+1>>b+1;
int n = strlen(a + 1), m = strlen(b + 1);
for(int i=1;i<=m;i++) sum[i] = sum[i-1] + (b[i] == '0');
LL ans = 0;
for(int i=1;i<=n;i++)
{
if(a[i] == '1') ans += sum[m - (n - i)] - sum[i - 1];
else ans += m - n + i - sum[m - (n - i)] - i + 1 + sum[i-1];
}
cout<<ans;
return 0;
}
CF608A
记录从第i楼出发的乘客的到达时间的最大值
从上到下枚举楼层，如果当前这一层楼的所有乘客都到了。就直接下楼 —— ans++
否则就等到乘客到了位置，再下楼——ans = max(ans,f[i]) + 1
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 1005;
int n,s,x;
int f[N],t[N];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>s;
for(int i=1;i<=n;i++) cin>>x>>t[i],f[x] = max(f[x],t[i]);
int ans = 0;
for(int i=s;i>=1;i--)
{
ans = max(ans,f[i]);
ans ++;
}
cout<<ans;
return 0;
}
//
CF606B
阅读题
按照给出的序列走，问第k次走到的点在之前是否走过，并问最后的时候有多少个点没有走过
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 5005;
int n,m;
int x,y;
string s;
bool st[N][N];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>x>>y;
cin>>s;
int len = s.size(), cnt = 1;
st[x][y] = 1;
cout<<1<<' ';
for(int i=0;i<len-1;i++)
{
if(s[i] == 'U' && x > 1) x--;
if(s[i] == 'D' && x < n) x ++;
if(s[i] == 'L' && y > 1) y --;
if(s[i] == 'R' && y < m) y ++;
if(!st[x][y]) cout<<1<<' ',cnt++;
else cout<<0<<' ';
st[x][y] = 1;
}
cout << n * m - cnt;
return 0;
}
//
CF606A
每两个同色剩余可以换一个欠的
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 0;
int a[5],b[5],c[5];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 3;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int add = 0,sub = 0;
for(int i=1;i<=n;i++) c[i] = a[i] - b[i];
for(int i=1;i<=n;i++)
{
if(c[i] < 0) sub += c[i];
if(c[i] > 0) add += c[i] / 2;
}
// cout<<add<<' '<<sub<<endl;
if(add + sub >= 0) cout<<"Yes";
else cout<<"No";
return 0;
}
//
CF554B
如果这两行是一样的，整列翻转只有长的也一样
#include <bits/stdc++.h>
using namespace std;
unordered_map<string,int> h;
string s;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>s,h[s]++;
int res = 0;
for(auto x : h)
res = max(res,x.second);
cout<<res;
return 0;
}
CF456B
\((1^n + 2^n + 3^n + 4^n) \mod 5 = (1^n \mod 5 + 2^n \mod 5 + 3^n \mod 5 + 4^n \mod 5) \mod 5\)
根据费马小定理：\(a^{5-1} \equiv 1 (mod \;5)\)
所以原式 $ = (1^{n; mod;4} + 2^{n; mod;4} + 3^{n; mod;4} + 4^{n; mod;4}) \mod 5$
最后打个高精模吗，搞定
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 0;
int mod(string a,int b)//高精度a除以单精度b
{
int d=0;
for(int i=0;i<a.size();i++) d=(d*10+(a[i]-'0'))%b; //求出余数
return d;
}
int power(int x,int y)
{
int ans = 1;
for(int i=1;i<=y;i++) ans *= x;
return ans;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
string n;
cin>>n;
int mi = mod(n,4);
LL ans = (power(2,mi) % 5 + power(3,mi) % 5 + power(4,mi) + 1) % 5;
cout<<ans;
return 0;
}
//
CF456A
按价格排序，维护质量前缀最大值，发现前缀最大值比 \(b_i\) 大，就Happy，反之亦然
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI = 3.1415926535;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f3f3f;
const int dx4[5] = {0, 1, 0, -1}, dy4[5] = {1, 0, -1, 0};
const int dx8[10] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[10] = {1, 1, 0, -1, -1, -1, 0, 1};
const int pow10[15] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int N = 1e5;
PII a[N];
int n;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
sort(a+1,a+1+n);
for(int i=1;i<n;i++)
{
if(a[i].first < a[i+1].first && a[i].second > a[i+1].second)
{
cout<<"Happy Alex";
return 0;
}
}
cout<<"Poor Alex";
return 0;
}
//