A.链接：https://ac.nowcoder.com/acm/contest/4462/A
来源：牛客网
给出一个长度无限的数列，初始全部为零，有三种操作：
增加操作：给下标为 tt 的数加 cc 。特别注意，如果在下标 [t-30,t+30]内有不为零的数，增加操作无效。
削减操作：让数列中下标最小的不为零数变为零。
查询操作：查询数列中下标为 tt 的数字是多少。
输入描述:
第一行包含一个整数 N,1 \le N \le 10^6N,1≤N≤10
6
，表示操作总数。
随后 N 行，每行由两个数字或一个数字组成。
若一行中有两个数字，分别代表增加操作的 t,c 。
若一行中只有数字-1，执行削减操作。
若一行中只有一个不为 -1的数字，则代表查询操作的数字 t。
保证t，c均为非负整数且在整形范围内。
输出描述:
削减操作时，先输出该数字，再变为零
若序列元素全为零，则削减操作无效，此时输出 “skipped”
查询时，输出该位置上的数
示例1
输入
7
140 1
120 2
100 3
120
100
-1
100
输出
0
3
3
0
题意：不难理解
思路：我看蒙佬用set+pair做的，很是强悍！为室友点赞
#include <bits/stdc++.h>
using namespace std;
set<pair<int,int> > st;
int main()
{
int n;
cin >>n;
while(n--)
{
int t,c,flag=0;
char ss;
cin>>t;
scanf("%c",&ss);
if(ss==' ')
{
flag=1;// 说明有两个数
cin >>c;
}
if(flag)//执行的是添加操作
{
if(!st.size()) st.insert(make_pair(t,c));//一开始都是0，第一个肯定执行
else//筛选后面的增加操作是否能执行
{
int ff=1;
auto top=st.lower_bound(make_pair(t,0));//找到第一个大于等于0的地址。
if(top == st.begin())
{
if(abs(st.begin()->first-t)<=30) ff=0;//不符合
}
else
{
auto res=top--;
if(abs(res->first-t)<=30||abs(top->first-t)<=30) ff=0;//不符合
}
if(ff) st.insert(make_pair(t,c));//符合则存入
}
}
else if(t==-1)
{
if(st.size()) cout <<st.begin()->second<<endl,st.erase(st.begin());
else puts("skipped");
}
else
{
auto top=st.lower_bound(make_pair(t,0));
if(top->first==t) cout <<top->second<<endl;
else cout <<0<<endl;
}
}
}
B.链接：https://ac.nowcoder.com/acm/contest/4462/B
来源：牛客网
题目描述
给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。
输出描述:
仅包含一个数，表示我们所需要的答案。
示例1
输入
5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5
输出
4
说明
样例中最大子链为1 -> 2 -> 5
备注:
一个结点，也可以称作一条链
思路：让dp[i]代表从iii结点到以其为根的子树中任意一个点的路径最大值
val[i]为i节点的点权，child[i][j]为i节点的第j个儿子的编号
则动态转移方程为 dp[i]=max(dp[child[i][j]]+val[i],f[i],val[i])
另外要有一个更新ans的代码ans=max(ans,dp[u]+dp[x]);
这条语句一定要放在更新dp[u]之前，因为dp[u]+dp[x]是当前根的左子树或者右子树的长度的最大值，如果更新完dp[u]，那么dp[u]就代表着左子树加上右子树的最大值了
没错！又是俺宿舍蒙佬的，让俺嫖了，没咋看懂，回头问问
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v[100005];
ll a[100005],dp[100005],ans=-0x3f3f3f3f;
ll maxx=-0x3f3f3f3f;
void dfs(ll u,ll f)
{
dp[u]=a[u];
for(int i=0;i<v[u].size();i++)
{
int x=v[u][i];
if(x==f) continue;
dfs(x,u);
ans=max(ans,dp[u]+dp[x]);
dp[u]=max(dp[u],dp[x]+a[u]);
}
ans=max(ans,dp[u]);
}
int main()
{
int n;
cin >>n;
for(int i=1;i<=n;i++) cin >>a[i];//输入点
for(int i=1;i<n;i++)//输入边，构造图
{
ll x,y;
cin >>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
cout <<ans<<endl;
}
D
链接：https://ac.nowcoder.com/acm/contest/4462/D
来源：牛客网
我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。
假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。
你只能沿着 x 轴或 y 轴方向移动，从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1,j)，(i,j+1) 或 (i,j-1) 距离增加 1。
输入描述:
在第一行中给出一个T, 1 \le T \le 10T,1≤T≤10, 代表测试数据的组数。
对于每组输入，在第一行中给出房间大小，第二行给出你的初始位置。
接下来给出一个正整数 n,1 \le n \le 10n,1≤n≤10 代表纸片的个数。
接下来 n 行，每行一个坐标代表纸片的位置。
保证房间小于 20 \times 2020×20，纸片一定位于房间内。
输出描述:
对于每组输入，在一行中输出答案。
格式参见样例。
示例1
输入
1
10 10
1 1
4
2 3
5 5
9 4
6 5
输出
The shortest path has length 24
思路：DFS求得所有路径然后跟新得到最小值就行了
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 100;
pair<int,int> ans[maxn];
bool vis[maxn];
int res = 0;
int p,x,y;
int getdis(int x,int y,int x1,int y1){
return abs(x-x1)+abs(y-y1);
}
void dfs(int n,int fx,int fy,int len){
if(n == p){
len += getdis(x,y,fx,fy);
if(len < res) res = len;
return ;
}
for(int i=1;i<=p;i++){
if(vis[i])continue;
vis[i] = true;
dfs(n+1,ans[i].first,ans[i].second,len + getdis(fx,fy,ans[i].first,ans[i].second));
vis[i] = false;
}
}
int main(){
int t;cin>>t;
while(t--){
res = inf;
memset(vis,false,sizeof(vis));
int n,m;
cin>>n>>m;
cin>>x>>y;
cin>>p;
for(int i=1;i<=p;i++){
cin>>ans[i].first>>ans[i].second;
}
dfs(0,x,y,0);
cout<< "The shortest path has length "<<res<<endl;
}
}
E
水题：找规律
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n,m;
int r,c;
while(cin>>n>>m>>r>>c){
cout<<(ll)(n-r)*(m-c)<<endl;
}
}
F
签到
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n,d;
while(cin>>n>>d){
ll ans = 1;
cout<<n;
for(ll i=1;i<=d;i++){
cout<<"00";
}
cout<<endl;
}
}
G
仓库选址
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxn = 110;
const int inf = 0x3f3f3f3f;
ll sum[maxn];
ll num[maxn][maxn];
int mp[maxn][maxn];
int main()
{
int t;
int n,m;
scanf("%d",&t);
while(t--)
{
ll ans = 1e18+10;
ll res = 0;
scanf("%d%d",&m,&n);
memset(num,0,sizeof(num));
memset(sum,0,sizeof(sum));
for(int i = 0;i<n;++i)
{
for(int j = 0;j<m;++j)
{
scanf("%d",&mp[i][j]);
sum[i] = sum[i]+mp[i][j];
}
}
for(int i = 0;i<m;++i)
{
for(int j = 0;j<n;++j)
{
for(int k = 0;k<m;++k)
{
num[j][i]+=abs(i-k)*mp[j][k];
}
}
}
/*cout<<endl; for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { cout<<num[i][j]<<' '; } cout<<endl; }*/
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
res = 0;
for(int k = 0;k<n;++k)
{
res+=abs(i-k)*sum[k];
res+=num[k][j];
}
ans = min(ans,res);
}
}
cout<<ans<<endl;
}
return 0;
}
H
#include<iostream>
#include<vector>
#include<map>
using namespace std;
const int N=100010;
vector<int>add[N],de[N];
map<int,int> vis;
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int l,r,w;
cin>>l>>r>>w;
add[l].push_back(w);
de[r+1].push_back(w);
}
int cnt=0;
int ans=0;
int maxx=-1e6;
for(int i=1;i<=n;i++)
{
for(auto j:add[i])
{
if(vis[j]==0)
cnt++;
vis[j]++;
}
for(auto j:de[i])
{
vis[j]--;
if(vis[j]<=0)
cnt--;
}
if(cnt>maxx)
{
maxx=cnt;
ans=i;
}
}
printf("%d\n",ans);
return 0;
}
J
思路：有时候python也是解决问题的一种很好用的语言
大爱python！！！！重拾
n=int(input())
for i in range(0,n):
k=input()
tot=0
flag=0
for j in k:
if j=='+':
tot=tot+1
else:
if j>='0' and j<='9':
Q=0
else:
flag=1
if flag==1 or tot!=1 or k[0]=='+' or k[len(k)-1]=='+':
print("skipped")
else:
l=k.split('+')
if int(int(l[0]))+int(l[1])==0:
print("0")
else:
print(int(int(l[0])+int(l[1])))
京公网安备 11010502036488号