上海理工大学校内选拔赛（重现赛）
天气预报
还没补
A+B Problem
找最大值和第二大的值，不是最大值的元素加上最大值，是最大值的元素加上第二个最大值即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define x first
#define y second
int a[1000005];
#define all(v) v.begin(),v.end()
signed main(){
std::ios::sync_with_stdio(0);
vector<pii>ve;
std::cin.tie(0);
int n; cin>>n;
int maxx=-1;
int pos;
for(int i=0;i<n;i++) {
cin>>a[i];
maxx=max(maxx,a[i]);
if(maxx==a[i]) pos=i;
}
int max2=-1;
int pos2;
for(int i=0;i<n;i++)
{
if(i!=pos) max2=max(max2,a[i]);
if(max2==a[i]) pos2=i;
}
for(int i=0;i<n;i++){
if(i!=pos&&i!=pos2) a[i]+=maxx;
else{
if(i==pos) a[i]+=max2;
else a[i]+=maxx;
}
}
for(int i=0;i<n;i++) cout<<a[i]<<" ";
}
Komorebi的数学课
理解快速幂的过程，\(n*n\quad mod\quad n+2=(n\quad mod \quad n+2)*(n\quad mod \quad n+2)mod \quad n+2\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define x first
#define y second
#define all(v) v.begin(),v.end()
int mod;
int qpow(int a,int n){
int res=1;
while(n)
{
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
mod=n+2;
cout<<qpow(n,n)%mod;
}
次佛锅
我分别处理食材单词和数字，然后最后再一起放到map里面
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define x first
#define y second
#define all(v) v.begin(),v.end()
int mod;
signed main(){
string s; getline(cin,s);
vector<string>ve;
map<string,int>mp;
for(int i=0;i<s.size();i++)
{
if(islower(s[i])||isupper(s[i])){
string sb;
int j=i;
while(isupper(s[j])||islower(s[j])&&j<s.size())
{
sb+=s[j];
j++;
}
ve.push_back(sb);
i=j;
}
}
vector<int>num;
for(int i=0;i<s.size();i++)
{
if(isdigit(s[i]))
{
int j=i,cnt=0;
while(isdigit(s[j])&&j<s.size())
{
cnt=cnt*10+s[j]-'0';
j++;
}
i=j;
num.push_back(cnt);
}
}
int n; cin>>n;
// for(auto t:ve) cout<<t<<" ";
// for(auto t:num) cout<<t<<" ";
for(int i=0;i<ve.size();i++)
{
mp[ve[i]]+=num[i];
}
// for(auto t:mp) cout<<t.x<<" "<<t.y<<endl;
while(n--)
{
string ss; cin>>ss;
cout<<mp[ss]<<endl;
}
}
黄金律法
排序，最大的加最小的即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define x first
#define y second
#define all(v) v.begin(),v.end()
int mod;
int a[100005];
int b[100005];
signed main(){
int t; cin>>t;
while(t--)
{
int sum1=0,sum2=0;
int n; cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
sort(a,a+n);
sort(b,b+n,greater<int>());
for(int i=0;i<n;i++) sum1+=a[i]*b[i];
cout<<sum1<<endl;
}
}
Setsuna的K数列
1.对于\(1 ,3, 4，9，10，12， 13.....\)我们可以发现在三进制下对应的数字为\(001，010，011，100，101，110，111\)，突然发现当我们把一个十进制位的数，比如n=5时转化为二进制\(101\)时，恰好是对应的三进制的第五个数。
2.那么只需要把这个n下的二进制位，看成三进制位，然后转化为一个十进制数即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define x first
#define y second
#define all(v) v.begin(),v.end()
int mod=1000000009;
int qpow(int a,int n)
{
int res=1;
while(n)
{
if(n&1) res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
signed main(){
int n,k;
cin>>n>>k;
int ans=0;
for(int i=0;i<=31;i++)
{
if(n>>i&1)
{
ans+=qpow(k,i);//快速幂计算每一位比如3的i次方
ans=ans%mod;
}
}
cout<<ans;
}
史东薇尔城
1.使用dijkstra跑点1到其他点点最短路就行。但是注意一点，这个题目的数据有问题，v和w并不是在1-n的，所以开图的时候要建大一点，不然就会有段错误
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
struct DIJ{
using i64=long long;
using pii=pair<i64,i64>;
vector<i64>dis;//存点到点的最小距离
vector<vector<pii> >G;//存起点和终点的编号，边权
DIJ() {}//防止默认状态报错，类似vector<int>a,
//为dijkstra初始化
DIJ(int n)
{
dis.assign(n+1,1e18);//把所有元素设置为1e18
G.resize(n+1);//把G的大小设置为n+1
}
void add(int u,int v,int w){
G[u].emplace_back(v,w);//u v为点，w为边权
}
//堆优化版的dijkstra
void dijkstra(int s) {
priority_queue<pii> que;
dis[s] = 0;
que.push({0, s});
while (!que.empty()) {
auto p = que.top();
que.pop();
int u = p.second;
if (dis[u] < p.first) continue;
for (auto [v, w] : G[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
que.push({ -dis[v], v});
}
}
}
}
};
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
int n,m;
cin>>n>>m;//
DIJ dij(100005);//只找一个点这样初始化，多个点建vector<DIJ>dij
//如果你只开了n的大小就会段错误，题目数据v w可能大于n
for(int i=0;i<m;i++)
{
int u,v,w;
cin>>u>>v>>w;
dij.add(u,v,w);
dij.add(v,u,w);
}
dij.dijkstra(1);
int q; cin>>q;
while(q--)
{
int u,v; cin>>u>>v;
cout<<dij.dis[u]+dij.dis[v]<<endl;
}
}
Wiki下象棋
1.思路其实就是跑两次bfs，但是注意把象棋对应方向的下一步是否有障碍判断一下，直接在8个方向上建上对应的方向数组即可
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
int n,m,k,a,b,c,d;//k为障碍物(a,b)起点 (c,d)终点
bool ck(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=m;
}
//注意这里的tx，ty是对应dx，dy数组的，不可以顺序混搭
int dx[]={-2,-2,1,-1,2,2,1,-1};
int dy[]={-1,1,-2,-2,-1,1,2,2};
int tx[]={-1,-1,0,0,1,1,0,0};
int ty[]={0,0,-1,-1,0,0,1,1};
//------------------------------------
int mp[310][310];//障碍
bool st[310][310];
int dis[310][310];
//跑国际马
int bfs1()
{
memset (st,0,sizeof st);
memset(dis,0x3f,sizeof dis);
queue<pii>q;
q.push({a,b});
dis[a][b]=0;
st[a][b]=1;
while(q.size()){
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<8;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(ck(nx,ny)&&!mp[nx][ny]&&!st[nx][ny])
{//符合范围，日字点不能放障碍，不能被走过
q.push({nx,ny});
dis[nx][ny]=dis[x][y]+1;
st[nx][ny]=1;
}
}
}
if(dis[c][d]>1e9) return -1;
return dis[c][d];
}
//跑象棋马
int bfs2()
{
memset(dis,0x3f,sizeof dis);
memset(st,0,sizeof st);
queue<pii>q;
q.push({a,b});
dis[a][b]=0;
st[a][b]=1;
while(q.size()){
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<8;i++){
int nx=x+dx[i],ny=y+dy[i];
int mx=x+tx[i],my=y+ty[i];
if(ck(nx,ny)&&!mp[nx][ny]&&!st[nx][ny]){
if(!mp[mx][my]){//象棋马比国际马需要多考虑一个因素
q.push({nx,ny});
dis[nx][ny]=dis[x][y]+1;
st[nx][ny]=1;
}
}
}
}
if(dis[c][d]>1e9) return -1;
return dis[c][d];
}
void solve()
{
memset(mp,0,sizeof mp);
cin>>n>>m>>k>>a>>b>>c>>d;
while(k--)
{
int x,y; cin>>x>>y;
mp[x][y]=1;
}
int ans1=bfs1();
int ans2=bfs2();
cout<<ans1<<" "<<ans2<<endl;
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}