Divisible Pairs
你有两个整数 x , y x,y x,y 和一个长为 n n n 的数组 a a a。
你需要求出有多少个正整数对 ( i , j ) (i,j) (i,j) 满足:
- 1 ≤ i < j ≤ n 1 \le i < j \le n 1≤i<j≤n
- a i + a j a_i + a_j ai+aj 可被 x x x 整除
- a i − a j a_i - a_j ai−aj 可被 y y y 整除
t t t 组数据, 1 ≤ t ≤ 1 0 4 , 1 ≤ n ≤ 2 × 1 0 5 , ∑ n ≤ 2 × 1 0 5 , 1 ≤ a i , x , y ≤ 1 0 9 1 \le t \le 10^4 ,1 \le n \le 2 \times 10^5,\sum n \le 2 \times 10^5,1 \le a_i,x,y \le 10^9 1≤t≤104,1≤n≤2×105,∑n≤2×105,1≤ai,x,y≤109。
思路
因为两个数相减可以被 y 整除,我们可以得到,两个数对 y 进行取模后得到的值一定是相等的,所以我们按照 a i % y a_i\%y ai%y 进行分类,然后去统计满足相加为 x 的情况,我们同样知道,两个数相加可以被 x 整除 ,即为两个数对 x 进行取模后,相加为 x ,所以我们遍历每个值,若当前值为 k ,那么加上 x-k 的出现次数即可。
因为每个数都是取模后的情况,所以对于 0 这种情况计算其本身的数量即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
void solve()
{
int n,x,y;
cin>>n>>x>>y;
vector<ll> a(n);
for(auto &ai: a) cin>>ai;
map<int,map<int,int> > mp;
ll ans=0;
for(auto ai: a){
int c1=ai%x,c2=ai%y;
if(c1==0) ans+=mp[c2][c1];
else ans+=mp[c2][x-c1];
mp[c2][c1]++;
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
Anna and the Valentine’s Day Gift
Anna 和 Sasha 在玩游戏,他们有一个长度为 n n n 的数组 a a a。
Anna 为先手。两人分别操作:
- 轮到 Anna 时,她首先需要选择一个 a i a_i ai,并将其按照数位翻转,并省略前导零。例如 42 42 42 翻转为 24 24 24, 1580 1580 1580 翻转为 851 851 851。这样操作后, a a a 数组大小不变。
- 轮到 Sasha 时,他需要选择 a i , a j ( i ≠ j ) a_i, a_j(i \ne j) ai,aj(i=j),并以任意顺序将其连接。例如 2007 2007 2007 和 19 19 19 可以连接为 200719 200719 200719 或 192007 192007 192007。这样操作后, a a a 数组大小减一。
玩家不能跳过回合。当 a a a 中只剩下一个整数时,如果它大于等于 1 0 m 10^m 10m,Sasha 获胜。否则 Anna 获胜。
如果 Anna 和 Sasha 都以最优方式操作,谁会获胜?
思路
考虑A对结果的影响,对于有后缀 0 的数字,其操作后会减少后缀 0 个数的长度,其他的数字则没有任何影响。
考虑B对结果的影响,若B想要赢,则其应该尽可能的将后缀 0 个数多的数拼起来。
所以本质上是计算后缀 0 的组数,以及每一组内有多少个后缀 0 。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
void solve()
{
int n,m;
cin>>n>>m;
int cnt=0;
vector<int> p;
vector<int> a(n);
for(auto &ai: a) cin>>ai;
for(int i=0;i<n;i++){
int x=a[i];
vector<int> tmp;
while(x){
tmp.push_back(x%10);
x/=10;
cnt++;
}
int cur=0;
for(auto &t:tmp){
if(t==0) cur++;
else break;
}
p.push_back(cur);
}
int sum=0;
sort(p.begin(),p.end(),greater<int>());
for(int i=0;i<p.size();i+=2){
sum+=p[i];
}
if(cnt-sum>m){
cout<<"Sasha"<<endl;
}
else cout<<"Anna"<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}
Chat Screenshots
给出 n n n 个人进行的聊天室中, k k k 个人做的截图,每个截图中截图者都在第一位置,其后各位按照发帖时间前后确定。判断这些聊天室截图是否自洽(即能确定至少一种可能的发帖顺序)。
思路
如果不自洽,说明出现了环,所以我们只需要对题目给出的进行建边,然后判断是否有环即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"
int tot, dfsn[N], ins[N], low[N];
stack<int> s;
vector<int> e[N];
vector<vector<int>> scc;
vector<int> b(N);
void dfs(int x)
{
low[x] = dfsn[x] = ++tot, ins[x] = 1, s.push(x);
for (auto u : e[x])
{
if (!dfsn[u])
{
dfs(u);
low[x] = min(low[x], low[u]);
}
else if (ins[u])
low[x] = min(low[x], dfsn[u]);
}
if (dfsn[x] == low[x])
{
vector<int> c;
while (1)
{
auto t = s.top();
c.push_back(t);
ins[t] = 0;
s.pop();
b[t] = scc.size();
if (t == x)
break;
}
// sort(c.begin(), c.end(),greater<ll>());
scc.push_back(c);
}
}
void add(int u,int v)
{
e[u].push_back(v);
}
void solve()
{
int n,k;
cin>>n>>k;
vector<vector<int> > a(k+5,vector<int> (n+5));
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
for(int j=2;j<=n-1;j++) add(a[i][j],a[i][j+1]);
}
for(int i=1;i<=n;i++){
if(!dfsn[i]) dfs(i);
}
int ok=1;
for(auto u: scc){
if(u.size()>1){
ok=0;
break;
}
}
if(ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
for(int i=0;i<=n;i++){
e[i].clear();
dfsn[i]=low[i]=ins[i]=0;
}
tot=0;
scc.clear();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
solve();
}
system("pause");
return 0;
}