(B)N^N (简单快速幂模板,直接套用就行)
点击查看代码
#include<iostream>
using namespace std;
long long a, b,n;
int main()
{
cin >> n;
while(n--)
{
scanf("%lld", &a);
signed long long A = a%10,sum=1;
while (a)
{
if (a & 1) sum = A*sum%10;
A = A*A%10;
a >>= 1;
}
cout << (sum + 10)%10;
cout << endl;
}
return 0;
}
点击查看代码
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
string s;
stack<char> a;
bool isoperator(char ch)
{
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == ')' || ch == '(')
return true;
else
return false;
}
int getpre(char ch, bool flag) //按照运算顺序分级
{
if (ch == '+' || ch == '-')
return 1;
if (ch == '*' || ch == '/')
return 2;
if (ch == '(' && flag)
return 0;
if (ch == '(' && !flag)
return 3;
}
int main()
{
cin >> s;
for (int i = 0; i < s.size(); i++)
{
if (!isoperator(s[i]))
{
cout << s[i];
continue;
}
else
{
if (a.empty())
{
a.push(s[i]);
continue;
}
else
{
if (s[i] == ')')
{
while (a.top() != '(' && !a.empty()) // 遇到 )将( 前所有元素输出,再删除(
{
cout << a.top();
a.pop();
}
a.pop();
continue;
}
while (!a.empty() && getpre(s[i], 0) <= getpre(a.top(), 1))
{
cout << a.top();
a.pop();
}
a.push(s[i]);
}
}
}
while (!a.empty())
{
cout << a.top();
a.pop();
}
return 0;
}
点击查看代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 11;
int next1[N],n,m;
char p[N],s[N];
void ne()
{
next1[1] = 0; //存储串中最长前后缀长度
for (int i = 2, j = 0; i <= n; i++) // i扫描串,j扫描前缀
{
while (j && p[i] != p[j + 1]) //从1开始存所以加1
j = next1[j];//回跳前一位
//遍历串,当i与j+1为不同时,j 跳至匹配位置,若无跳至0
if (p[i] == p[j + 1]) j++; //相等时J++,指向前缀末尾
next1[i] = j;
}
}
int pi()
{
for (int i = 1, j = 0; i <= m; i++) //遍历主串
{
while (j && s[i] != p[j + 1]) j = next1[j];
if (s[i] == p[j + 1]) j++;
if (j == n) //前缀与字串长度一致时,找到位置
{
printf("%d\n", i - n + 1);
return 0;
//j=next1[j]; //重新寻找字串
}
}
return 1;
}
int main()
{
for(int i=0;i<3;i++)
{
cin >> s + 1 >> p + 1;
m = strlen(s + 1);
n = strlen(p + 1);
ne();
int k = pi();
if (k) cout << 0 << endl;
}
//for (int i = 1; i <= n; i++)
// cout << next1[i] << ' ';
return 0;
}
点击查看代码
#include<iostream>
using namespace std;
#define LL long long
LL a, b, x, y;
LL ex(LL a, LL b, LL& x, LL& y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
LL r = ex(b, a % b, y, x);
y -= a / b * x;
return r;
}
int main()
{
cin >> a >> b;
ex(a, b, x, y);
cout << (x % b+b)%b;
return 0;
}
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int Max=500005;
int n,m,k,d,head,tail,l,r,mid,maxlen,minlen,now,tag;
int x[Max],num[Max],f[Max],p[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');
c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;isdigit(c);c=getchar())
x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline bool check(int len)
{
now=0,head=1,tail=0,maxlen=len+d,minlen=max(d-len,1);
for(int i=1;i<=n;i++)
{
while(x[now]<=x[i]-minlen)
{
if(f[now]<=-1e9)
{
now++;
continue;
} //不能到达now
while(head<=tail&&f[now]>=f[p[tail]])
tail--;
p[++tail]=now,now++; //放进队列
}
while(head<=tail&&x[p[head]]<x[i]-maxlen)
head++;
if(head<=tail)
f[i]=f[p[head]]+num[i];
else
f[i]=-1e9;
if(f[i]>=k)
return 1; //有满足的直接返回
}
return 0;
}
int main()
{
n=get_int(),d=get_int(),k=get_int();
for(int i=1;i<=n;i++)
x[i]=get_int(),num[i]=get_int();
l=0,r=500000;
while(l<r) //二分答案
{
mid=(l+r)>>1;
if(check(mid)) tag=1,r=mid;
else l=mid+1;
}
if(tag)
cout<<r;
else
cout<<"-1\n";
return 0;
}