A. Another A+B Problem
暴力枚举出所有的情况,然后特判一下
#include <bits/stdc++.h>
using namespace std;
set<string> res;
int t;
string a , b , c = "????????";
#define f(d) ((d[0]-'0')*10 + d[1]-'0' + (d[3]-'0')*10 + d[4]-'0' == (d[6]-'0')*10 + d[7]-'0' )
void dfs(string p, const vector<int> &flag, int i) {
if (p.size() > t) return;
if (p.size() == t) {
sort(p.begin(), p.end());
do {
string d = c;
for (int i = 0, j = 0; i < 8; i++)
if (d[i] == '?') d[i] = p[j], j++;
int ss = 0;
for( int i = 0 ; i < 8 ; i ++ )
if( d[i] == a[i] && (b[i] == 'P' || b[i] == 'B') ){
ss = 1;
break;
}
if( ss ) continue;
if (f(d))res.insert(d);
} while (next_permutation(p.begin(), p.end()));
return;
}
if (i >= 10) return;
if (flag[i]) {
dfs(p, flag, i + 1);
return;
}
while (p.size() <= t) {
dfs(p, flag, i + 1);
p.push_back(i + '0');
}
return;
}
int main() {
cin >> a >> b;
vector<int> cnt(10);
vector<int> flag(10, 0);
for (int i = 0; i < 8; i++) {
if (b[i] == 'G') c[i] = a[i];
else if (b[i] == 'B') flag[a[i] - '0'] = 1;
else cnt[a[i] - '0']++;
}
for (auto i: c) if (i == '?') t++;
string p = "";
for (int i = 0; i <= 9; i++) {
for (; cnt[i]; cnt[i]--) p.push_back(i + '0');
}
dfs(p, flag, 0);
cout << res.size() << "\n";
for( auto i : res )
cout << i << "\n";
return 0;
}
E. Expenditure Reduction
预处理出每个字母的位置,然后 dp 转移一下
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[305];
void solve(){
string a,b;
cin>>a>>b;
int n=a.size();
int m=b.size();
a=' '+a;
b=' '+b;
vector<int>mp[300];
for(int i=m;i>=1;i--){
mp[b[i]].push_back(i);
}
for(int i=1;i<=m;i++)dp[i]=-0x3f3f3f3f;
int ans=0x3f3f3f3f3f,l=0;
for(int i=1;i<=n;i++){
dp[0]=i;
for(auto it:mp[a[i]]){
dp[it]=max(dp[it],dp[it-1]);
}
if(i-dp[m]+1<=ans){
ans=i-dp[m]+1;
l=dp[m];
}
}
for(int i=0;i<ans;i++){
cout<<a[l+i];
}
cout<<"\n";
//cout<<ans<<"\n";
}
int32_t main() {
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
G. Gua!
计算出可能造成伤害的最大值。
#include <bits/stdc++.h>
using namespace std;
void solve(){
double b,r,d,s;
cin>>b>>r>>d>>s;
if(d==0){
cout<<"ok\n";
return ;
}
if(r==0||b==0) {
cout << "gua!\n";
return ;
}
if(b+b*(long long)(s*r/60)>=d)cout<<"ok"<<endl;
else cout<<"gua!"<<endl;
}
int main(){
int T;
cin >> T;
while ( T -- )
solve();
}
H. Heirloom Painting
统计出所有颜色相同的段,长度除以\(k\)上取证就是这一段需要的染色次数。注意最后一次染色的段的长度一定大于等于\(k\)。
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n , m , k;
cin >> n >> m >> k;
vector<int> a(n);
for( auto & i : a ) cin >> i;
vector<pair<int,int>> cnt;
int t = 1 , last = a[0];
for( int i = 1 ; i < n ; i ++ ){
if( a[i] == last ) t ++;
else {
cnt.emplace_back( last , t );
t = 1 , last = a[i];
}
}
cnt.emplace_back( last , t );
if( cnt.size()>=2&&cnt.back().first == cnt.front().first ){
cnt.front().second += cnt.back().second;
cnt.pop_back();
}
int f = 0 , res = 0;
for( auto [l,t] : cnt ){
if( t >= k ) f = 1;
res += (t+k-1) / k;
}
if( f ) cout << res << "\n";
else cout << "-1\n";
}
int main(){
int T;
cin >> T;
while ( T -- )
solve();
}
M. My University Is Better Than Yours
这题应该是图论比较板的题?但是我图论会的不太多,所以学了一个不用图论的做法。首先我们每次遍历一列。把这列中所有没有访问过的点加入到队列中。如果累计访问过的点的数量等于当前的列数,说明当前队列中的点构成了一个环,更新队列中点的答案后,把队列清空即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n , m;
cin >> n >> m;
vector<vector<int>> a( m+1 , vector<int>(n+1) );
for( int i = 1 ; i <= m ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
cin >> a[i][j];
vector<int> q , vis( n+1 ) , res( n+1 );
for( int i = 1 , cnt = 0 , rank = 1 ; i <= n ; i ++ ){
for( int j = 1 ; j <= m ; j ++ )
if( !vis[ a[j][i] ] ) vis[a[j][i]] = 1 , cnt ++ , q.push_back( a[j][i] );
if( cnt == i ){
for( auto j : q )
res[j] = n - rank;
q = vector<int>() , rank = i + 1;
}
}
for( int i = 1 ; i <= n ; i ++ )
cout << res[i] << " ";
return 0;
}
N. Nine Is Greater Than Ten
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
void solve(){
string a,b;
cin>>a>>b;
if(a>b){
cout<<a<<">"<<b;
}
else if(a==b)cout<<a<<"="<<b;
else cout<<a<<"<"<<b;
}
int32_t main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T=1;
while(T --)
solve();
return 0;
}
- Programming Collegiate Shanghai Contest 2022programming collegiate shanghai contest programming collegiate provincial contest programming collegiate jiangsu contest programming collegiate contest guilin programming collegiate mianyang contest international programming collegiate contest programming collegiate shenzhen contest 2022 programming collegiate acm-icpc programming collegiate contest harbin programming collegiate codeforces contest