D - Johnny and Contribution
题目大意
给你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; }
E - Johnny and Grandmaster
题目大意
给你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\n",num); } return 0; }
