2023年国际大学生程序设计竞赛（ACM-ICPC）新疆赛区

文章目录

• A
• B
• C
• D
• E
• F
• G
• H
• I
• J

A

B

C

D

E

就是两个map直接循环遍历就可以只要当前被标记过就可以直接用，否则的话就去找最小的数，也就是从1开始逐个加，而且我们如果在后边遇到相同的数可以用map直接找到。

#include
using namespace std;
map<int,int> mp1;
map<int,int> mp;
int a[100010];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}int ans=1;for(int i=1;i<=n;i++){if(mp1[a[i]]!=0){cout<<mp1[a[i]]<<" ";continue;}while(mp1[a[i]]==0){//cout<<1<if(mp[ans]!=0){ans++;continue;}if(mp[ans]==0){mp1[a[i]]=ans;mp[ans]++;}}cout<<mp1[a[i]]<<" ";}cout<<endl;return 0;
}

F

要求整行和整列都是回文的，那么我们就用四个角，化成享用的字母后然后往里边缩，【队友写的】

#include 
#define N 1005
#define int long long
using namespace std;
char a[N][N];
signed main()
{int n, m;cin >> n >> m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin >> a[i][j];}}int ans = 0;for(int i=1;i<=n/2;i++){for(int j=1;j<=m/2;j++){vector<int> p(4);p[0] = a[i][j] - 'a';p[1] = a[i][m+1-j] - 'a';p[2] = a[n+1-i][j] - 'a';p[3] = a[n+1-i][m+1-j] - 'a';int mn = 0x3f3f3f3f;for(int k=0;k<26;k++){int cnt = 0;for(int l=0;l<4;l++)cnt += min(abs(p[l]-k),abs(26-abs(p[l]-k)));mn = min(mn, cnt);}ans += mn;}}if(n & 1){int i = (n + 1) >> 1;for(int j=1;j<=m/2;j++){int mn = 0x3f3f3f3f;for(int k=0;k<26;k++){int cnt = 0;cnt += min(abs(a[i][j]-'a'-k),abs(26-abs(a[i][j]-'a'-k)));cnt += min(abs(a[i][m+1-j]-'a'-k),abs(26-abs(a[i][m+1-j]-'a'-k)));mn = min(mn, cnt);}ans += mn;}}if(m & 1){int j = m + 1 >> 1;for(int i=1;i<=n/2;i++){int mn = 0x3f3f3f3f;for(int k=0;k<26;k++){int cnt = 0;cnt += min(abs(a[i][j]-'a'-k),abs(26-abs(a[i][j]-'a'-k)));cnt += min(abs(a[n+1-i][j]-'a'-k),abs(26-abs(a[n+1-i][j]-'a'-k)));mn = min(mn, cnt);}ans += mn;}}cout << ans;return 0;
}

G

#include 
#define mod 1000000007
#define int long long
using namespace std;
int ksc(int a, int b)
{a = a % mod;b = b % mod;int res = 0;while(b){if(b & 1) res = (res + a) % mod;b >>= 1;a = (a + a) % mod;}return res;
}
signed main()
{int n, k; cin >> n >> k;vector<int> a(k + 1), b(k + 1);int ans = 0;int t = 1;while(t < n) t <<= 1;t >>= 1;int cnt = 0;int rem = 0;for(int i=1;i<=k;i++) {cin >> a[i] >> b[i];if(cnt + a[i] <= t) cnt += a[i], ans += ksc(b[i], a[i]), ans %= mod;else if(cnt >= t){rem += ksc(b[i], a[i]);rem %= mod;}else{int num = t - cnt;ans += ksc(b[i], num) , ans %= mod;rem += ksc(b[i], (a[i] - num)), rem %= mod;cnt = t;}}cout << (ksc(ans, ans) + ksc(rem, rem)) % mod;
}

H

找规律，不难发现是一个等差数列，运用等差数列求和公式在用取余的原理就可以得出结果

#include
using namespace std;
#define int long long
signed main()
{int n,m,l;cin>>n>>m>>l;int sum=(n)*(n+1)/2;int k=n-(m-1);int r=(k)*(k+1)/2;r=(sum-r+l)%26;if(r==0){cout<<"Z";return 0;}char c='A'+r-1;cout<<c<<endl;return 0;
}

I

要使消耗的最小，那么就得从最小的开始，所以直接从1开始，如果遇到重合了直接跳过，如果用到了就打个标记vis

#include 
#define int long long
using namespace std;
signed main()
{int n; cin >> n;vector<int> vis(n + 1);vector<int> d(n + 1);for(int i=1;i<=n;i++){cin >> d[i];}int ans = 0;int tmp = 1;int cnt = 0;for(int i=2;i<=n;i++){while(tmp <= n && (vis[tmp] == d[tmp] && tmp != i || tmp == i)) tmp ++;if(tmp == n + 1 || vis[i] == d[i]){cout << -1; return 0;}vis[tmp] ++;vis[i]++;ans += tmp * tmp + i * i;cnt ++;if(cnt == n - 1) break;}cout << ans;return 0;
}

J

#include
using namespace std;
typedef long long ll;
const ll N=1e6+10;
const ll inf  = 0x3f3f3f3f;
vector<ll> v[N];
ll deep[N];
ll ans=0;
void dfs(ll t, ll f){deep[t] = deep[f] + 1;if(deep[t] >= 2) ans++;ll x = v[t].size();if(t != 1) x--;ans += (x * (x - 1))/2;for(auto i : v[t]){if(i != f){dfs(i, t);}}
}
int main()
{ll n,m;ll a,b;cin>>n;for(int i=1;i<n;i++){cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}deep[0]=-1;dfs(1,0);cout<<ans<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！