问题 A: A.博弈论 [ABC148F] Playing Tag on Tree
题目描述
有一个n个节点的树，刚开始邱宇站在x号点，妹妹站在y号点。
邱宇先手，两人交替地行动。每次需要移动到相邻的位置。如果两人在某一点相遇，则游戏结束。
邱宇希望游戏尽量晚地结束，妹妹希望游戏尽量早地结束。若两人使用最优策略，则妹妹会移动多少次？
输入
第一行三个数，分别是节点数量n，邱宇的起点x和妹妹的起点y。
接下来n-1行，每行两个数表示树的一条边。
数据保证是一颗树，2<=n<=100000，x!=y。
输出
输出一个非负整数表示妹妹将会移动多少次。
样例输入
样例输入1： 5 4 1 1 2 2 3 3 4 3 5 样例输入2： 5 4 5 1 2 1 3 1 4 1 5 样例输入3： 2 1 2 1 2 样例输入4： 9 6 1 1 2 2 3 3 4 4 5 5 6 4 7 7 8 8 9
样例输出
样例输出1： 2 样例输出2： 1 样例输出3： 0 样例输出4： 5
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e5 + 7;
int n, u, v, x, y, vis[N], ans[N], m; // 声明变量n, u, v, x, y, vis数组, ans数组, m
vector<int> w[N]; // w为大小为N的整型向量数组
//若一个点到u的距离小于它到v的距离 那么T就不会在这里被A追上
//u是T的起点 v是A的起点
void dfs(int a, int b, int c){ // 定义DFS函数，参数为当前节点编号a，距离b，标志位c
if(c)
vis[a] = b; // 如果标志位c为1，将当前节点标记为已访问，并记录距离在vis数组中
else
ans[a] = b; // 如果标志位c为0，记录距离在ans数组中
for(int i = 0; i < w[a].size(); i++){ // 遍历当前节点a的相邻节点
if(c && !vis[w[a][i]] && w[a][i] != v) // 如果标志位c为1且相邻节点未被访问过且不等于目标节点v
dfs(w[a][i], b + 1, c); // 以相邻节点为新的当前节点，距离b+1，标志位c，进行递归调用dfs函数
else if(!c && !ans[w[a][i]] && w[a][i] != u) // 如果标志位c为0且相邻节点未被访问过且不等于起始节点u
dfs(w[a][i], b + 1, c); // 以相邻节点为新的当前节点，距离b+1，标志位c，进行递归调用dfs函数
}
}
int main(){
IOS; // 同步输入输出流
cin >> n >> u >> v; // 输入n, u, v
for(int i = 1; i < n; i++) // 循环读入n-1条边的信息
cin >> x >> y, w[x].push_back(y), w[y].push_back(x); // 将边的两个端点信息加入到w数组中
dfs(v, 0, 1), dfs(u, 0, 0); // 第一次DFS，计算从目标节点v到各个节点的距离；第二次DFS，计算从起始节点u到各个节点的距离
for(int i = 1; i <= n; i++) // 遍历所有节点
if(vis[i] > ans[i]) // 如果从目标节点到达某节点的距离大于从起始节点到达该节点的距离
// vis[i]记录的是i到v的距离
m = max(m, vis[i]); // 更新最大距离m
printf("%d", m - 1); // 输出最大距离减去1
return 0;
}
问题 B: B.分发礼物 [ABC148C] Snack
题目描述
codeforces.com/problemset/problem/4/A分西瓜这道题想必大部分人已经做过了。
邱宇正在和实验室的大伙分西瓜。已知要分西瓜的总人数将会是A或者B（都有可能），邱宇希望平均地分配给每个朋友整数斤的西瓜。
请你输出最少需要多少斤西瓜，才能满足对于两种情况都能满足条件地分配。
输入
输入一行两个整数A，B。
保证1<=A,B<=10^5，A不等于B
输出
输出一个整数表示你的答案。
样例输入
样例输入1： 2 3 样例输入2： 123 456 样例输入3： 100000 99999
样例输出
样例输出1： 6 样例输出2： 18696 样例输出3： 9999900000
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int a,b;cin>>a>>b;
cout<<a*b/__gcd(a,b);
return ;
}
signed main(){
int t=1;
while(t--)solve();
return 0;
}
问题 C: C.石头剪刀布 [ABC149D] Prediction and Restriction
题目描述
邱宇正在和妹妹玩石头剪刀布。如果用石头获胜，他将会获得R分。如果用剪刀获胜，他将获得S分。如果用布获胜，他将获得P分。如果输了或者平局将不得分也不扣分。
由于妹妹不太聪明，她将会按照特定的字符串出石头，剪刀或布。具体地，数据会给你一个字符串T，字符串的第i位是r，p，s时，妹妹将会在第i轮出石头，布或者剪刀。
虽然优势很大，但是邱宇也有一点点劣势：在前K轮中，可以任意地出。但是在K轮之后，他不能出的和第(i-K)轮一样。
例如第1轮出了石头，K=3，那么他第4轮将不能再出石头。
优势如此之大，邱宇想让你帮他算算他最多能获得多少分？
输入
第一行两个正整数N，K表示玩多少局和限制因素K。
第二行三个正整数R，S，P分别表示出石头、剪刀或者布，并且获胜时，邱宇能获得的分数。
第三行一个长为N的字符串表示妹妹的每一轮的出法。
保证2<=N<=10^5，1<=K<=N-1，1<=R,S,P<=10^4,字符串的长度恰好为N，字符串中只包含字符r,p,s。
输出
输出最多能获得几分。
样例输入
样例输入1： 5 2 8 7 6 rsrpr 样例输入2： 7 1 100 10 1 ssssppr 样例输入3： 30 5 325 234 123 rspsspspsrpspsppprpsprpssprpsr
样例输出
样例输出1： 27 样例输出2： 211 样例输出3： 4996
#include <bits/stdc++.h>
using namespace std;
//读清楚题
void solve() {
int n, k;
cin >> n >> k;
int a, b, c;cin >> a >> b >> c;
//出石头 剪刀 布且获胜
//r s p 那妹妹要出
//s p r
string s;cin >> s;
s=' '+s;
int ans = 0;
for (int i = 1; i <= k; i++) {
if (s[i] == 'r') ans += c;
if (s[i] == 's') ans += a;
if (s[i] == 'p') ans += b;
}
for (int i = k+1; i <=n; i++) {
if (s[i] == s[i - k]) {
s[i] = 'x'; //如果重复就还称x 使得下一次不会重复
} else {
if (s[i] == 'r') ans += c;
if (s[i] == 's') ans += a;
if (s[i] == 'p') ans += b;
}
}
cout << ans << '\n';
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while (t--)solve();
return 0;
}
问题 D: D.异或和的和 [ABC147D] Xor Sum 4
题目描述
这是一个简单的异或和的和的问题。
给你N个数字，求ΣAi XOR Aj(i<j)对10^9+7的余数。其中XOR表示亦或。
输入
第一行一个整数N。
第二行N个整数表示数组A。
保证2<=N<=3*10^5，0<=Ai<2^60。
输出
输出一个整数表示你的答案。
样例输入
样例输入1： 3 1 2 3 样例输入2： 10 3 1 4 1 5 9 2 6 5 3 样例输入3： 10 3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
样例输出
样例输出1： 6 样例解释1： (1 XOR 2)+(1 XOR 3)+(2 XOR 3)=3+2+1=6 样例输出2： 237 样例输出3： 103715602
#include <bits/stdc++.h>>
#define int long long
const int mod = 1e9+7;
using namespace std;
const int N = 3e5+7;
int a[N];
//a开到了2^60说明用位运算了
void solve(){
int n;cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
int ans = 0;
for (int i = 0; i < 60; i++){ //对于每一个位置
int cnt = 0;
for (int j = 1; j <= n; j++) {
if (a[j] & (1ll << i)) {//如果有一个这个位置是1cnt就++
cnt++;//相同
}//意思就是如果是1的话
}//(2的i次方)*cnt *(n-cnt)
ans=(ans + ((1ll << i)%mod*cnt%mod * (n - cnt) % mod))%mod;//一个位置上1的个数乘以0的个数实际上可以用来表示这些数两两异或异或的一种形式
}
cout << ans << '\n';
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--)solve();
return 0;
}
问题 E: E.吃饼干 [ABC149B] Greedy Takahashi
题目描述
邱宇有A个饼干，妹妹有B个饼干。
妹妹将会循环K次以下动作：
- 如果邱宇还有饼干，则吃邱宇的其中一块
- 否则，如果自己还有饼干，吃自己的其中一块
- 否则，什么也不做
请问最后邱宇和妹妹各自还剩多少饼干。
输入
输入一行三个整数：A，B，K
保证0<=A，B，K<=10^12（ABK三个数都满足这个条件）
输出
输出一行两个整数表示答案
样例输入
2 3 3
样例输出
0 2
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int a,b,k;cin>>a>>b>>k;
if(a>=k){cout<<a-k<<" "<<b;return ;}
if(b>=k-a){cout<<"0 "<<b+a-k;return ;}
cout<<"0 0";
return ;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
while(t--)solve();
return 0;
} 问题 F: F.abs(全排列-全排列) [ABC150C] Count Order
题目描述
全排列和字典序应该不用再介绍了。。。
总而言之，你有两个长为N的排列，他们在全排列中都有一席之地，你需要输出他们在按字典序排列的全排列中的排名之差。
123和321谁排第一呢？出题人不想管了，所以决定让你abs一下。
输入
第一行一个正整数N
第二行一个长为N的排列表示排列A
第三行一个长为N的排列表示排列B
数据保证2<=n<=8
输出
输出一个非负整数表示他们排名的差值
样例输入
样例输入1： 3 1 3 2 3 1 2 样例输入2： 8 7 3 5 4 2 1 6 8 3 8 2 5 4 6 7 1 样例输入3： 3 1 2 3 1 2 3
样例输出
样例输出1： 3 样例输出2： 17517 样例输出3： 0
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
string a, b;
for(int i=0;i<n;i++){char ch;cin>>ch;a+=ch;}
for(int i=0;i<n;i++){char ch;cin>>ch;b+=ch;}
string c = a;
sort(c.begin(), c.end());
int cnt = 0;
int ans1 = 0;int ans2 = 0;
do {//记得要用do while语句进入循环
cnt++;
if (c == a) ans1 = cnt;
if (c == b) ans2 = cnt;
if (ans1 && ans2) break;
} while (next_permutation(c.begin(), c.end()));
cout << abs(ans1 - ans2)<< '\n';//记得加abs()
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while(t--) solve();
return 0;
}
问题 G: G.重排 [ABC163E] Active Infants
题目描述
一个长为n的数组，你需要将其重新排列，使得总贡献最大。
其中一个数字ax如果之前排在了第x个位置，移动后排在了第y个位置，则会获得Ax*|x-y|的贡献。
输入
第一行一个正整数n。
接下来一行n个数，表示初始的数组。
保证2<=n<=2000,1<=ai<=10^9
输出
一行一个整数表示最大的总贡献。
样例输入
样例输入1： 4 1 3 4 2 样例输入2： 6 5 5 6 1 1 1 样例输入3： 6 8 6 9 1 2 1
样例输出
样例输出1： 20 样例解释1： 将a1移动到a3,a2移动到a4，a3移动到a1，a4移动到a2，则会获得1*|1-3|+3*|2-4|+4*|3-1|+2*|4-2|=20 样例输出2： 58 样例输出3： 85
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e3+9 ;
const ll mod = 1e9+7 ;
const ll INF = 1e18 ;
ll Abs( ll x ){ return x < 0 ? -x : x ; }
ll dp[ N ][ N ] , n ;//dp[i][j]表示将区间[i, j]的数字重新排序后所能获得的最大贡献值
//只在这[l,r]范围中调整
pair<ll,ll>a[ N ] ;
void solve(){
cin >> n ;
for( int i = 1 ; i <= n ; i ++ ){
cin >> a[ i ].first ;
a[ i ].second = i ;
}
sort( a+1 , a+1+n ) ;
for( int len = 1 ; len <= n ; len ++ ) {
for( int l = 1 , r = len ; r <= n ; l++ , r ++ ) {//左右端点
if( l == r ) {// 左端点==右端点
dp[l][r] = a[len].first * Abs(l - a[len].second) ;
} else {
dp[ l ][ r ] = max( dp[l+1][r] + a[len].first * Abs(l - a[len].second),
dp[l][r-1] + a[len].first * Abs(r - a[len].second) );//移动到两个极端 看看哪个大
}
}
}
cout << dp[1][n] << "\n" ;
}
int main(){ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
ll tt = 1 ; //cin >> tt ;
while( tt-- ) solve() ;
return 0 ;
}
