2021CCPC 哈尔滨
J. Local Minimum
对每个位置的数判断一下 是否是其所在的行和列中最小的数即可
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int board[1010][1010];
void solve()
{
int n,m;
cin >> n >> m;
vector<int> x(n+10,1e18);
vector<int> y(m+10,1e18);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> board[i][j];
x[i] = min(x[i],board[i][j]);
y[j] = min(y[j],board[i][j]);
}
}
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(board[i][j]==x[i]&&board[i][j]==y[j]) ans++;
}
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
B. Magical Subsequence
枚举和，因为数据范围是[1,100],所以和的范围是[2,200]。
按数存位置，枚举第二个数，我们要尽可能的让第二个数靠左，每次到j就看看能不能在前面找到值位(sum - a[j])的数。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N];
vector<int> idx[110];
int n;
void solve()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
idx[a[i]].push_back(i);
}
int ans = 0;
for(int i=2;i<=200;i++)
{
//cout << i << endl;
int l = 0;
int sum = 0;
for(int j=1;j<=n;j++)
{
if(i-a[j]<=0 || i-a[j]>100 || j <= l) continue;
int pos = upper_bound(idx[i-a[j]].begin(),idx[i-a[j]].end(),l) - idx[i-a[j]].begin();
if(pos==idx[i-a[j]].size())continue;
pos = idx[i-a[j]][pos];
if(pos<j)
{
sum++;
l = j;
}
}
ans = max(sum,ans);
}
cout << ans*2 << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
E. Power and Modulo
根据数据范围，很显然我们可以找到M，找不到就是不存在。找到了就按题意跑一遍看他符不符合就行了。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;
void solve()
{
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
bool ok = false;
int ans = 0;
for(int i=1;i<=n;i++)
{
if(a[i]==0&&(!ok))
{
ans = (1ll << (i-1));
ok = true;
}
if(ok&&a[i]!=0)
{
cout << -1 << endl;
return;
}
}
map<int,int> idx;
int len = 0;
for(int i=1;i<=n;i++)
{
if(a[i] != (1ll << (i-1)))
{
ans = (1ll << (i-1)) - a[i];
if(ans < 0)
{
cout << -1 << endl;
return;
}
if(i>=2 && ans <= (1ll >> (i-2)))
{
int q = (1ll >> (i-2)) / ans;
ans = ans * (q + 1);
if(ans>=(1ll >> (i-1)))
{
cout << -1 << endl;
return;
}
}
break;
}
}
if(ans==0)
{
cout << -1 << endl;
return;
}
int sum = 1;
for(int i=1;i<=n;i++)
{
sum %= ans;
if(sum!=a[i])
{
cout << -1 << endl;
return;
}
sum <<= 1;
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
D. Math master
易知 ap=bq ,通过数据范围我们很容易发现我们可以通过二进制枚举算出p中删掉的位数进而求出a，再通过前述公式求出b。此时问题就变成了b是不是q中的子序列，求解判断即可。
注意：会爆LL,用ull更会死，最好开int128,要自己写输入输出
#include <bits/stdc++.h>
#define endl '\n'
#define int __int128
using namespace std;
int p,q;
char sp[30],sq[30];
int delp[10],delq[10];
int lenp,lenq;
int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10ll);putchar(x%10+'0');}
bool check(int x){
for(int i = lenq-1;i>=0;i--)
{
if(x%10==(sq[i]-'0'))
{
x/=10;
continue;
}
delq[sq[i]-'0']++;
}
if(x) return false;
for(int i=0;i<10;i++)
{
if(delp[i]!=delq[i]) return false;
}
return true;
}
void solve()
{
scanf("%s%s",sp,sq);
lenp = strlen(sp);
lenq = strlen(sq);
p = 0,q = 0;
for(int i=0;i<lenp;i++) p = p * 10 + sp[i] - '0';
for(int i=0;i<lenq;i++) q = q * 10 + sq[i] - '0';
int x = p , y = q;
for(int i=0;i<(1ll<<lenp);i++)
{
for(int j=0;j<10;j++)
{
delq[j] = delp[j] = 0;
}
int a=0,b;
for(int j=0;j<lenp;j++)
{
if(i >> j & 1)
{
delp[sp[j] - '0']++;
}
else
{
a = a*10 + (sp[j] - '0');
}
}
if(a==0 || q*a%p) continue;
b = q*a/p;
if(check(b))
{
x = min(x,a);
y = min(y,b);
}
}
//cout << p << "! " << q << " " << sp << "? " << sq << endl;
write(x);putchar(' ');
write(y);putchar('\n');
}
signed main(){
int T = 1;
T = read();
while(T--) solve();
return 0;
}