+a的次数=k%2+k/2
-b的次数=k/2
注意数据不要爆范围了
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int t;
int k,a,b;
int main(){
cin>>t;
while(t--){
cin>>a>>b>>k;
cout<<(long long)(a-b)*(k 2)+(k%2)*a<<endl; }return 0; } < code></(long></cstdio></cstring></iostream>
设所求答案为x
则 (n|x) (10^k|x)
又因为x要为最小正整数
所以可以求lcm(n,10^k)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,k,t;
long long gcd(long long a,long long b){
return b==0?a:gcd(b,a%b);
}
int main(){
cin>>t;
while(t--){
cin>>n>>k;
int m=pow(10,k);
cout<<(long long)n*m gcd(n,m)<<endl; } return 0; < code></(long></cmath></cstring></iostream></cstdio>
读题时以为很难结果自己吓自己就….
其实此题与滑雪这道题很相似（记忆化搜索）
只需要加以修改
问的QWER经历的最多，所以求的是最长路径
三种情况
判环的方法
1.强连通分量
2.topsort
3.dfs
4.spfa(it died)
(事先把QWER的位置换为0，1，2，3)
我们枚举每个(i,j)
以i,j为起点，找最长路，dfs判断有没有环
假设求出的最长路的长度为t
则QWER出现的次数
此时如果起点为(mp[i][j])
为1，次数为(\lfloor {\frac{t}{4} }\rfloor)
为2，次数为(\lfloor \frac{t-3}{4} \rfloor)
为3，次数为(\lfloor{\frac{t-2}{4} }\rfloor)
为4，次数为(\lfloor{ \frac{t-1}{4} }\rfloor)
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
const int maxn=1e3+10;
int mp[maxn][maxn];
int f[maxn][maxn];
bool st[maxn][maxn];
bool huan=0;
int nxt[4]={0,0,1,-1},nyt[4]={-1,1,0,0};
int dp(int x,int y){
if(huan) return -1;
if(f[x][y]!=-1) return f[x][y];
st[x][y]=1;
f[x][y]=1;
for(int i=0;i<4;++i){ int nx="x+nxt[i],ny=y+nyt[i];" if(nx>=1 && ny>=1 && nx<=n && ny<="m" mp[nx][ny]="=(mp[x][y]+1)%4){//保证Q-W-E-R" if(st[nx][ny]){ 有环 huan="1;return" -1; } f[x][y]="max(f[x][y],dp(nx,ny)+1);" st[x][y]="0;" return f[x][y]; int main(){ cin>>n>>m;
for(int i=1;i<=n;++i) for(int j="1;j<=m;++j){" char c;cin>>c; //用数值代替
if(c=='Q') mp[i][j]=0;
if(c=='W') mp[i][j]=1;
if(c=='E') mp[i][j]=2;
if(c=='R') mp[i][j]=3;
}
memset(f,-1,sizeof(f));
int res=0;
for(int i=1;i<=n;++i) for(int j="1;j<=m;++j){" int t="dp(i,j);//t为路径长度" if(mp[i][j]) t-="4-mp[i][j];" res="max(t/4,res);" } if(huan) puts("infinity"); else if(res="=0)" puts("none"); cout<<res<<endl; return 0; < code></=n;++i)></=n;++i)></=n></4;++i){></iostream></cstring></cstdio>
赛后总结
1.不能无脑写上去，加以分析，欲速则不达
2.学会转化为做过的题目
3.仔细读题（读了个寂寞）
ZFY AK IOI
Original: https://www.cnblogs.com/guiyou/p/15228019.html
Author: 归游
Title: AcWing 第15场周赛
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584578/
转载文章受原作者版权保护。转载请注明原作者出处！