题目大意
给你m个顶点，n条边的无向图，每个顶点都有自己的期望w[i]，将图中所有点填入数字，规则是在填任意一点时，其填入的数字是从1开始且这个点的邻居没有的最小数字，输出填图的顺序。
解题思路
首先，将所有期望是1的点全部填入1，将与其有一条边连接的点都填入2，若其中有点的期望值不是2，则说明不存在这种图，即直接退出，输出-1。 以此类推，每次都将上一个期望值的邻居填入此次的期望值，每次记录填入数字的点，并判断是否符合该点的期望即可。
代码
#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
vector<int>v[500005];
vector<int>vv[500005];
vector<int>ans;
int ss[500005];
int w[500005];
int main()
{
ll n,m;
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
int c;
scanf("%d",&c);
vv[c].push_back(i);
w[i]=1;
}
for(int i=1;i<=n;i++){
for(auto j:vv[i]){
if(w[j]!=i){
cout<<"-1";
return 0;
}
for(auto u:v[j]){
if(w[u]==i)w[u]++;
}
ans.push_back(j);
}
}
for(auto i:ans){
cout<<i<<" ";
}
return 0;
}题目大意
给你n个数字k[i]，再给你一个p，问你将k这个数组分成两部分，使两个部分的p的k[i]次方的差最小，问该差值最小是几？最终结果需要mod1000000007。
解题思路
该问题在可以转化为求把一串数字分成两串，是两者的差值最小，由于该数组有p的幂次方组成，因此其中大数的影响一定比小数的影响大，分两种情况，1、大数减去其后的所有小数的num值大于等于0，则最终答案就是该num值。2、大数减去其后的小数的num值小于0，则需要在相减的过程中，如果出现num=0并且后面还有数字时，把前面的全部抛弃，将大数改为后一个小数（即当在减k[i]的p次的过程中等于0，则将k[i+1]的p次设为大数）。以此类推，最后得到的num，就是最小值。
注意点：1、数字范围较大，在求幂的时候需要用快速幂。 2、在相减过程中，会出现差值num=1000000007的情况，此时会出现误判0，所以需要在引入一个余数，来保证该差值num真的为0.
代码
#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll fastpow(ll a,ll n,ll o)
{
ll base=a;
ll res=1;
while(n){
if(n&1)
res=(res*base)%o;
base=(base*base)%o;
n>>=1;
}
return res%o;
}
ll k[1000006];
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
ll t,n,p;
ll e=12345678;
scanf("%lld",&t);
while(t--){
scanf("%lld %lld",&n,&p);
for(int i=1;i<=n;i++){
scanf("%lld",&k[i]);
}
sort(k+1,k+n+1,cmp);
ll num=0,num2=0;
for(int i=1;i<=n;i++){
ll temp=(fastpow(p,k[i],MOD)+MOD)%MOD;
ll temp2=(fastpow(p,k[i],e)+e)%e; //防止误判
if(num==0&&num2==0){
num=temp;
num2=temp2;
}else{
num=(num+MOD-temp)%MOD;
num2=(num2+e-temp2)%e;
}
}
printf("%lld
",num);
}
return 0;
}