思路：
很显然答案是(1-1/(n^m))%mod,因为是除法取模所以是(n^m - 1)*inv(n^m)即可。这题卡常，如果快速幂用两次必超时，用一次就可以过。
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
//1 - (1/n)^m
ll ksm(ll a,ll b){
ll res = 1;
while(b){
if(b & 1)res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
ll inv(ll x){
return ksm(x,mod - 2);
}
void solved(){
ll n,m;scanf("%lld%lld",&n,&m);
ll ans = ksm(n,m);
printf("%lld\n", (ans - 1) * inv(ans) % mod);
}
int main(){
int t;
while(scanf("%d",&t) != EOF && t > 0){
while(t--)
solved();
}
return 0;
}
思路：打表找规律
可以发现abs(x-y)%3=0必败，其他必胜。
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long int ll;
void solved(){
int x,y;
scanf("%d%d",&x,&y);
int s = abs(x - y);
if(x == 0 && y == 0){
cout<<"awsl"<<endl;
return ;
}
if(s % 3 == 0){
cout<<"awsl"<<endl;
}else{
cout<<"yyds"<<endl;
}
}
int main(){
int t;
while(scanf("%d",&t) != EOF){
while(t--){
solved();
}
}
return 0;
}
思路：
a&b=y说明a,b的二进制至少大于等于y,所以a+b=x>=2y才有有结果，否则输出-1，a^b为x-全部二进制位相同的即x-2y，并且(x-2y)&y!=0才行因为当x=3,y=1,这种也是不符合情况的。
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long int ll;
void solved(){
ll x,y;scanf("%lld%lld",&x,&y);
if(x < 2 * y || ((x - 2 * y) & y) != 0){
cout<<"-1"<<endl;return ;
}
cout<<(x - 2 * y)<<endl;
}
int main(){
int t;scanf("%d",&t);
while(t--)
solved();
}
思路：
暴力比较+KMP就行了。
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long int ll;
const int maxn = 2e5 + 10;
int next[maxn];
vector<int> getnext(string t){
vector<int>next(t.size());
for(int i=1,k=0;i<t.size();i++){
while(k>0&&t[i]!=t[k]){
k=next[k-1];
}
if(t[i]==t[k]){
next[i]=++k;
}else{
next[i]=k;
}
}
return next;
}
int kmp(string t,string s){
int res = 0;
vector<int>next=getnext(t);
for(int i=0,k=0;i<s.size();i++){
while(k>0&&s[i]!=t[k]){
k=next[k-1];
}
if(t[k]==s[i]){
k++;
res = max(res,k);
}
if(k==t.size()){
return t.size();
}
}
return res;
}
void solved(){
string t,s;
cin>>t;
getnext(t);
int n;scanf("%d",&n);
int ans = 0;
for(int i = 1; i <= n; i++){
cin>>s;
ans += kmp(t,s);
}
printf("%d\n",ans);
}
int main(){
solved();
}
思路：
点与点之间建立双向边权为走路的时间，然后每个车站可以停的地方建立单向边，从源点s到汇点跑最短路即可。
为什么不能建立单向边呢？
随便举个例子就hack了。
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long int ll;
const int maxn = 2e5 + 10;
struct edge{
int v,w,next;
}e[maxn << 2];
int Time[maxn];
vector<int>G[maxn];
int head[maxn],tot;
void add(int u,int v,int w){
e[++tot].v = v;
e[tot].w = w;
e[tot].next = head[u];
head[u] = tot;
}
ll dis[maxn];
struct node{
ll id,dis;
bool operator < (const node &a)const{
return dis > a.dis;
}
};
void dij(int s,int t){
priority_queue<node>st;
st.push(node{s,0});
dis[s] = 0;
while(!st.empty()){
node cur = st.top();st.pop();
ll u = cur.id;
ll di = cur.dis;
if(cur.dis != dis[cur.id])continue;
for(int i = head[u]; i; i = e[i].next){
int v = e[i].v;
if(dis[v] > dis[u] + e[i].w){
dis[v] = dis[u] + e[i].w;
st.push(node{v,dis[v]});
}
}
}
cout<<dis[t]<<endl;
}
void solved(){
int n,m,s,t,T;scanf("%d%d%d%d%d",&n,&m,&s,&t,&T);
for(int i = 1; i <= n; i++)dis[i] = 1e9;
for(int i = 1; i <= m; i++){
scanf("%d",&Time[i]);
}
for(int i = 1; i <= n; i++){
if(i < n){
add(i + 1,i,T);
add(i,i + 1,T);
}
int x;scanf("%d",&x);
if(G[x].size() >= 1){
add(G[x].back(),i,Time[x]);
}
G[x].push_back(i);
}
dij(s,t);
}
int main(){
solved();
return 0;
}
思路：
很显然找最大连通块就行了，枚举顶点然后dfs跑它的连通块，相等的也记录一下。
时间复杂度O(n + m)。虽然枚举了顶点但是实际上只跑了一遍图。
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
const int maxn = 3e5 + 10;
int a[maxn];
vector<int>G[maxn];
bool vis[maxn];
int cnt;
vector<int>res;
void dfs(int u,int color,int f){
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(v == f)continue;
if(!vis[v] && a[v] == color){
vis[v] = true;
cnt++;
res.push_back(v);
dfs(v,color,u);
}
}
}
void solved(){
int n;scanf("%d",&n);
for(int i = 1; i <= n; i++)scanf("%d",&a[i]);
for(int i = 1; i <= n - 1; i ++){
int u,v;scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
cnt = 1;
int ans = 0;
vector<int>SS;
vector<int>add;
for(int i = 1; i <= n; i++){
if(!vis[i]){
res.push_back(i);
dfs(i,a[i],-1);
if(cnt == ans){
for(int k = 0; k < res.size(); k++){
add.push_back(res[k]);
}
}
if(cnt > ans){
ans = max(ans,cnt);
SS = res;
add.clear();
}
cnt = 1;
res.clear();
}
}
vector<int>cur;
for(int i = 0; i < SS.size(); i++){
cur.push_back(SS[i]);
}
for(int i = 0; i < add.size(); i++){
cur.push_back(add[i]);
}
sort(cur.begin(),cur.end());
printf("%d\n",(int)cur.size());
for(int i = 0; i < cur.size(); i++){
printf("%d ",cur[i]);
}
}
int main(){
solved();
return 0;
}
思路：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
不过这里求的是和的不同的个数，我们可以加一个维度表示能否得到这个数字，比如dp[i][j][x]就是(1,1)到(i,j)能不能得到x,true表示可以，false表示不行。转移方程为 dp[i][j][x] |= dp[i - 1][j][(x - a[i][j] + mod) % mod] | dp[i][j - 1][(x - a[i][j] + mod) % mod]。
最后枚举i从0到1e4 + 6找出dp[n][m][i]为真的计数即可。
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long int ll;
int a[1000][1000];
bool dp[110][110][20000];
int mod = 1e4 + 7;
int n,m;
void solved(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d",&a[i][j]);
a[i][j] %= mod;
}
}
dp[1][1][a[1][1]] = true;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
for(int m = 0; m < mod; m++){
if(i - 1 >= 1)
dp[i][j][m] |= dp[i - 1][j][(m - a[i][j] + mod) % mod];
if(j - 1 >= 1)
dp[i][j][m] |= dp[i][j - 1][(m - a[i][j] + mod) % mod];
}
}
}
int ans = 0;
for(int i = 0; i < mod; i++){
if(dp[n][m][i])ans++;
}
cout<<ans<<endl;
}
int main(){
solved();
}
思路：暴力模拟(偷懒了不想写了参考了一下别人的代码)
代码：
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long int ll;
const int maxn = 2e6 + 10;
char s[maxn];
int n;
int i;
ll dfs(){
ll ans = 0,num = 0;
for(; i <= n;i++){
ll cnt = 0;
while(i <= n && isdigit(s[i])) cnt = cnt * 10 + (s[i] - '0'),i++;
ans += num * (cnt > 0 ? cnt : 1);
num = 0;
if(isalpha(s[i])){
num = (s[i] - 'A' + 1);
}else if(s[i] == '('){
i++;
num = dfs();
}else break;
}
ans += num;
return ans;
}
int main(){
scanf("%s",s + 1);
n = strlen(s + 1);
i = 1;
cout<<dfs()<<endl;
return 0;
}
京公网安备 11010502036488号