A:拯救咕咕咕之史莱姆
题意：
思路：
5天之内，不是n天之内，所以这个求饶是在一段区间里面，注意到给的样例，73是求饶，77不是求饶，所以[74,76]可以试一下<=74求饶这样，最多试三次这题就过了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
ll n;
while(cin>>n && n!=0){
if(n <= 75){
cout<<"AOLIGEI!"<<endl;
}else{
cout<<"DAAAAAMN!"<<endl;
}
}
}
int main(){
solved();
return 0;
}B:烦人的依赖
题意：
思路：
很显然是一个拓扑排序，不过是对字符串拓扑排序，所以要先用map将字符串映射成数字，方便处理，然后就是裸的拓扑排序了，这题如果用两个map或者以上会超时，只能用一个，还有一个字典序小的先出，所以队列要改成优先队列。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
struct edge{
int v,next;
edge(){}
edge(int a,int b):v(a),next(b){}
}e[maxn];
int head[maxn],tot;
int deg[maxn];
bool vis[maxn];
void add(int u,int v){
e[++tot].v = v;
e[tot].next = head[u];
head[u] = tot;
}
void solved(){
int t;cin>>t;
for(int ca = 1; ca <= t; ca++){
tot = 0;
cout<<"Case #"<<ca<<":"<<endl;
int n,m;cin>>n>>m;
for(int i = 0; i <= m << 1; i++)e[i].v = 0,e[i].next = 0,head[i] = 0;
for(int i = 0; i <= n << 1; i++)deg[i] = 0;
string s;
vector<string>str;
map<string,int>mp;
for(int i = 1; i <= n; i++){
cin>>s;str.push_back(s);
}
sort(str.begin(),str.end());
for(int i = 0; i < str.size(); i++)mp[str[i]] = i;
for(int i = 1; i <= m; i++){
string s,t;cin>>s>>t;
add(mp[s],mp[t]);
deg[mp[t]]++;
}
priority_queue<int,vector<int>,greater<int> >st;
vector<int>ve;
int cc = 0;
for(int i = 0; i < str.size(); i++){
if(deg[i] == 0){
st.push(mp[str[i]]);
}
}
while(!st.empty()){
int u = st.top();st.pop();
ve.push_back(u);
cc++;
for(int i = head[u]; i ;i = e[i].next){
int v = e[i].v;
deg[v]--;
if(deg[v] == 0){
st.push(v);
}
}
}
if(cc < n){
cout<<"Impossible"<<endl;continue;
}
for(int i = 0; i < (int)ve.size(); i++){
cout<<str[ve[i]]<<endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solved();
return 0;
}C:异或生成树
题意：
思路：一开始题意理解错了找了任意两点的单链求异或值，事实上它要的是删掉一些点或者边剩下的树的所有节点异或值，考虑树上dp，先从叶子节点开始，计算异或值，然后一层一层把所有异或值传到树的上面去，(自下往上传)，定义dp[i][j]:以i为根节点的子树是否可以弄到异或值为j,转移方程：dp[u][i ^ j] = dp[u][i] && dp[v][j]。树上dp感觉每那么难理解，画一棵树然后模拟一下就知道，它把所有可能的子树的异或值都求出来了，然后取个max即可。
(第一次写树上dp，感觉不错(指赛后补题
代码：
#include<bits/stdc++.h>
using namespace std;
int a[130];
vector<int>G[130];
int dp[130][130];
int check[130];
//dp[i][j] : 以i为根节点的子树是否可以弄到异或值为j
void dfs(int u,int fa){
dp[u][a[u]] = 1;
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(v != fa){
dfs(v,u);
for(int i = 1; i <= 127; i++)check[i] = dp[u][i];
for(int i = 1; i <= 127; i++){//枚举根节点的异或值
for(int j = 1; j <= 127; j++){//枚举根节点的儿子节点的异或值
if(check[i] && dp[v][j])
dp[u][i ^ j] = 1;
}
}
}
}
}
void solved(){
int n;cin>>n;
for(int i = 1; i <= n ;i++)cin>>a[i];
for(int i = 1; i < n; i++){
int u,v;cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
int ans = 0;
for(int i = 1; i <= 127; i++){
for(int j = 1; j <= 127; j++){
if(dp[i][j])ans = max(ans,j);
}
}
cout<<ans<<endl;
}
int main(){
solved();
return 0;
}E:无敌阿姨
题目大意：
思路：
模拟题。。。。没什么好讲的，写不出来只能说明代码写少了(指我本人。
注意当这层的被子全部拿走了，然后即使m恢复全部体力并且<=k，默认他可以继续上一层楼
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
typedef long long int ll;
int a[maxn];
void solved(){
int t;cin>>t;
while(t--){
int n,m,k;cin>>n>>m>>k;
for(int i = 1; i <= n ;i++)cin>>a[i];
int ans = 1;
int t = m;
for(int i = 1; i <= n ; i++){
if(m >= a[i]){
m -= a[i];a[i] = 0;
}else{
a[i] -= m;//能带走多少被子就带走多少被子把~
ans++;
m = t;
i--;continue;
}
if(i == n)break;
if(m > k){
m -= k;
}else{
ans++;m = t;
}
}
cout<<ans<<endl;
}
}
int main(){
solved();
return 0;
}G:校车
题意：
思路：站点数量很显然是所有点去重后的数量，安排的座位数量是在某个时间点的最大人数 - 这个时间点下车人数。然后因为数很大，所有要离散化一下，离线的区间修改用差分就能完成了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
ll cnt[maxn << 2];
ll dif[maxn << 2];
ll delta[maxn << 2];
void add(ll l,ll r){
dif[l]++;dif[r + 1]--;
}
void solved(){
int t;cin>>t;
while(t--){
memset(delta,0,sizeof(delta));
memset(cnt,0,sizeof(cnt));
memset(dif,0,sizeof(dif));
int n;cin>>n;
map<ll,ll>mp;
vector<pair<ll,ll> >ve;
int c = 0;
for(int i = 1; i <= n; i++){
ll a,b;cin>>a>>b;
mp[a]++;mp[b]++;
ve.push_back(make_pair(a,b));
cnt[++c] = a;cnt[++c] = b;
}
sort(cnt + 1,cnt + 1 + c);
int len = unique(cnt + 1,cnt + 1 + c) - (cnt + 1);
ll max_size = 0;
for(int i = 0; i < n ;i++){
ll l = lower_bound(cnt + 1,cnt + 1 + len,ve[i].first) - (cnt);
ll r = lower_bound(cnt + 1,cnt + 1 + len,ve[i].second) - (cnt);
add(l,r);
delta[r]++;
}
ll ans = 0;
for(int i = 1; i <= n; i++){
dif[i] += dif[i - 1];ans = max(dif[i] - delta[i],ans);
}
map<ll,ll>::iterator it = mp.begin();
ll ans2 = 0;
for(;it!=mp.end();it++)ans2++;
cout<<ans2<<" "<<ans<<endl;
}
}
int main(){
solved();
return 0;
}H:中位因数
题意：
思路：
因为能整除x的数的中位数分布在sqrt(x)的两边，我们可以枚举每个数的倍数，那么这个数是它倍数的因子，那么它就有可能是它倍数的中位数，我们用a[j]表示最靠近sqrt(x)的值，一开始会距离sqrt(x)比较远，不断维护a[j]，让他接近sqrt(x)两边，然后把这两中位数存起来。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int f[maxn];
int a[maxn];
int mod = 1e9 + 7;
void solved(){
for(int i = 1; i <= 1e6 ; i++){
for(int j = i; j <= 1e6 ; j += i){
int u = i,v = j / i;
if(u > v)swap(u,v);
if(u > a[j]){
a[j] = u;
f[j] = (u + v) / 2;
}
}
}
//for(int i = 1; i <= 10; i++)cout<<f[i]<<endl;
for(int i = 1; i <= 1e6; i++)f[i] += f[i - 1] % mod;
int t;cin>>t;
while(t--){
int n;cin>>n;cout<<f[n]<<endl;
}
}
int main(){
solved();
return 0;
} 
京公网安备 11010502036488号